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
.
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.
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.
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 .
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.
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
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.
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With