math - Why the bit operation i & (-i) equals to rightmost bit?

Question

I learned Fenwick Tree algorithm and there was written "i & (-i) equals to rightmost bit".
For example, 3 & (-3) = 1, 48 & (-48) = 16..

I tested the result for i <= 64, and all values satisfied the condition.
But I don't know why the condition satisfies (proof) for all positive integer i.

Please tell me how to prove.

EDIT: You can assume that i is 32-bit integer (But 16-bit is ok). If so, the range of value i is 1 <= i <= 2^31-1.

Answer 1

Say you've got a two's complement binary number i:

0b1101001010000000

and you want to find -i. Well, -i is the number such that i + (-i) == 0. So what number has that property? Well, if you construct another number:

 i: 0b1101001010000000
-i: 0b0010110110000000

such that the rightmost set bit is the same as in i, all bits after that are 0, and all bits before that are the inverse of those in i:

 i: 0b11010010 1 0000000
-i: 0b00101101 1 0000000

then when you add these numbers together, the carries propagate off the left side of the number and just leave all 0 bits, so this is -i.

Now, what do we get if we & these numbers? Well, the trailing zeros & together to produce zeros. The bits on the left are opposites in i and -i, so they & together to produce zeros. But the rightmost set bit is 1 in both i and -i, so that's the only set bit in i & -i.

     i: 0b11010010 1 0000000
    -i: 0b00101101 1 0000000
i & -i: 0b00000000 1 0000000