Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

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.

like image 682
square1001 Avatar asked Jan 31 '17 23:01

square1001


People also ask

Why do we need bit operations?

Because they allow greater precision and require fewer resources, bitwise operators can make some code faster and more efficient. Examples of uses of bitwise operations include encryption, compression, graphics, communications over ports/sockets, embedded systems programming and finite state machines.

How does bit operation work?

A bitwise operation operates on two-bit patterns of equal lengths by positionally matching their individual bits. For example, a logical AND (&) of each bit pair results in a 1 if both the first AND second bits are 1. If only one bit is a 1, the result is 0.

Why is bit operations faster?

Basically, you use them due to size and speed considerations. Bitwise operations are incredibly simple and thus usually faster than arithmetic operations. For example to get the green portion of an rgb value, the arithmetic approach is (rgb / 256) % 256 .

What does bit shifting by 1 do?

Bitshifting shifts the binary representation of each pixel to the left or to the right by a pre-defined number of positions. Shifting a binary number by one bit is equivalent to multiplying (when shifting to the left) or dividing (when shifting to the right) the number by 2.


2 Answers

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
like image 187
user2357112 supports Monica Avatar answered Oct 28 '22 12:10

user2357112 supports Monica


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.

like image 31
harold Avatar answered Oct 28 '22 11:10

harold