CODEWITHSUNDEEP
mathbit-manipulation
square1001
square1001

Reputation: 1464

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

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.

Upvotes: 6

Views: 1794

Answers (3)

Matt Timmermans
Matt Timmermans

Reputation: 59184

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

Upvotes: 1

user555045
user555045

Reputation: 64904

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.

Upvotes: 2

user2357112
user2357112

Reputation: 280898

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

Upvotes: 10

Related Questions