So this question came to my mind as I was coding the LCA algorithm using sparse table.

Consider this code

```
int LCA(int u, int v)
{
if (depth[u] < depth[v]) swap(u, v);
for (int i = LOG; i >= 0; i--)
{
if (depth[u] - (1 << i) >= depth[v])
{
u = P[u][i];
}
}
if (u == v) return u;
for (int i = LOG; i >= 0; i--)
{
if (P[u][i] != P[v][i])
{
u = P[u][i];
v = P[v][i];
}
}
return P[u][0];
}
```

and this one

int po2[LOG + 1];
void Init()
{
po2[0] = 1;
for (int i = 1; i <= LOG; i++) po2[i] = po2[i - 1] * 2;
}
int LCA(int u, int v)
{
if (depth[u] < depth[v]) swap(u, v);
for (int i = LOG; i >= 0; i--)
{
if (depth[u] - po2[i] >= depth[v])
{
u = P[u][i];
}
}
if (u == v) return u;
for (int i = LOG; i >= 0; i--)
{
if (P[u][i] != P[v][i])
{
u = P[u][i];
v = P[v][i];
}
}
return P[u][0];
}

The only difference is that I used `1 << i`

in the first code and an initialized array in the second one to find the value of $$$2^i$$$. I wonder which one will have better performance.

Auto comment: topic has been updated by ldn060904 (previous revision, new revision, compare).The difference should be minimal and you should code the one that is easier for you. If I had to guess, I would say that binary shifting is faster, but it's really something you would have to test on large test cases. Focus on more important time saves :)

$$$\mathcal{O}(1)$$$ code that doesn't use memory almost always works faster than code that does use memory.