LCA using sparse matrix in O(logn) time

Question

[1]: https://www.geeksforgeeks.org/lca-for-general-or-n-ary-trees-sparse-matrix-dp-approach-onlogn-ologn/

for (int i=0; i<level; i++) 
    if ((diff>>i)&1) 
        v = parent[v][i];

In the above code, it only jumps to the 2^ith parent, when "(diff>>i)" is odd. Why is it so? How did we understand that only in case of odd "(diff>>i)", we have to jump?

Answer 1

First of all, this answer doesn't explain the snippet you shared.

I really didn't understand that part of code either. I am not sure the code there is buggy or not because this seems incorrect. I can share my function on that part, hopefully you might find it a bit easier to understand. I put some comment to ease your understanding.

int lcaQuery(int p, int q) {
    if(depth[p] < depth[q]) {
        swap(p, q);
    }

    // uplifting p at the same level/height of q
    for(int i = level - 1; i >= 0; i--) {
        if (depth[p] - (1 << i) >= depth[q]) {
            p = parent[p][i];
        }
    }

    // if already catch q, this is the LCA
    if (p == q) return p;

    // uplifting p and q until both of their parents are same and we reach the root
    for(int i = level - 1; i >= 0; i--) {
        if (parent[p][i] != -1 and parent[p][i] != parent[q][i]) {
            p = parent[p][i];
            q = parent[q][i];
        }
    }

    // since now both p and q are in the same level, return their parent
    return parent[p][0];
}