c++ - Can someone explain what these lines of code are doing?

Question

int64_t lstbt(int64_t val){ 
   int64_t msk = val&(val-1); 
   return log2(val^msk);
}

What does the msk actually computes, and why are we returning log of value xor msk?

Answer 1

To understand the function:

int64_t lstbt(int64_t val){ 
   int64_t msk = val&(val-1); 
   return log2(val^msk);
}

let us break it into smaller chunks.

First the statement val-1, by adding -1 to val, you flip (among others) the least significant bit (LSB), (i.e., 0 turns into 1, and vice-versa).

The next operation (val&(val-1)) applies an "and" bitwise. From the & operator we know that:

1 & 1  -> 1
1 & 0  -> 0
0 & 1  -> 0
0 & 0  -> 0

So either

1. val was initially ...0, and val - 1 is ....1, and in this case val&(val-1) produces ...0;

2. or var was initially ...1, and var - 1 is ....0, and in this case val&(val-1) produces ...0;.

So in both cases, val&(val-1) set to 0 the LSB of var. Besides that, another important change that val&(val-1) does is setting to 0 the first rightmost bit set to 1.

So let us say that val = xxxxxxxx10000 (it could have been xxxxxxxxx1000 as long as it showcases the right most bit set to 1), when msk=val&(val-1) then msk will be xxxxxxxx00000

Next, we have val ^ msk; a XOR bitwise operation, which we know that:

1 ^ 1  -> 0
1 ^ 0  -> 1
0 ^ 1  -> 1
0 ^ 0  -> 0

So because val will be something like xxxxxxxx10000 and msk xxxxxxxx00000, where the bits represented with 'x' from val will match exactly those from msk; the result of val ^ msk will always be a number with all bits set to 0 with exception for the only bit that will be different between val and msk, namely the right most bit set to 1 of val.

Therefore, the result from val ^ msk will always be a value that is a power of 2 (except when val is 0). A value that can be represent by 2^y = x, where y is the index of the right most bit set to 1 in val, and x is the result from val^msk. Consequently, log2(val^msk) gives back y i.e., the index of the right most bit set to 1 in val.