5

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.

square1001
  • 1,402
  • 11
  • 26

3 Answers3

9

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
user2357112
  • 260,549
  • 28
  • 431
  • 505
2

It even works for negative integers, it doesn't really matter, we can prove it for bitstrings in general.

First the i != 0 case:

Using string notation,

-(a10k) = (~a)10k (either by definition, or by working out -x = ~x + 1)

Note that a number that isn't 0 is always in the form a10k, that is, it start with "anything", then has a rightmost 1 followed by any number of zeroes (maybe zero zeroes).

Then,

a10k & (~a)10k = 10k ('a' cancels with its inverse)

For the 0 case, well, there is no rightmost 1 so it isn't in the result either.

harold
  • 61,398
  • 6
  • 86
  • 164
1

When you decrement a two's complement integer, you:

  1. Find the right-most 1 bit and set it to 0; and
  2. Set all the lower-order bits to 1

i-1, therefore, has all the 1 bits that i has, except the right-most one.

The complement, ~(i-1), therefore shares no 1 bits with i, except he rightmost one, so i & ~(i-1) contains only the right-most 1 bit in i.

This can be simplified a bit if we note that ~x = -x-1, so ~(i-1) = -(i-1)-1 = -i. So the right-most 1 bit in i is just i&-i

Matt Timmermans
  • 53,709
  • 3
  • 46
  • 87