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

Question

I had this in part of the code. Could anyone explain how i & (i ^ (i - 1)) could be reduced to i & (-i)?

Answer 1

i ^ (i - 1) makes all 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 (See Why does (x-1) toggle all the bits from the rightmost set bit of x?). The part before the last 1 bit is not changed when subtracting 1 from i, so xoring with each other returns 0 in that part, while the remaining will be 1 because of the difference in i and i - 1. After that i & (i ^ (i - 1)) will get the last 1 bit of i

-i will inverse all bits up to the last 1 bit of i because in two's complement -i == ~i + 1, and i & (-i) results the same like the 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

See also

• Why n bitwise and -n always return the right most bit (last bit)
• What does (number & -number) mean in bit programming?