Why is "i & (i ^ (i - 1))" equivalent to "i & (-i)"

Question

I had it in the code part. Can someone explain how i & (i ^ (i - 1)) can be reduced to i & (-i) ?

Answer 1

i ^ (i - 1) does all the bits after the last 1 bit of i becomes 1.

For example, if i has a binary representation as abc...de10...0 , then i - 1 will be abc...de01...1 in binary format. The part before the last 1 bit does not change when you subtract 1 from i, so xor ing returns 0 in this part with each other, while the rest will be 1 due to the difference in i and i - 1 . After that, i & (i ^ (i - 1)) will receive the last 1 bit of i

-i will invert all bits to the last 1 bit of i, because in the two additions -i == ~i + 1 and i & (-i) results will be the same as above

For example:

  20 = 0001 0100 19 = 0001 0011 20 ^ 19 = 0000 0111 = 7 20 & 7 = 0000 0100 -20 = 1110 1100 20 & -20 = 0000 0100