为什么要进行位操作(-i)等于最右边的位? [英] Why the bit operation i & (-i) equals to rightmost bit?

问题描述

我学习了Fenwick树算法，并写了"i&(-i)等于最右边的位".
例如，3 & (-3) = 1, 48 & (-48) = 16..

我测试了i <= 64的结果，所有值均满足条件.
但是我不知道为什么条件对于所有正整数i都满足(证明).

请告诉我如何证明.

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.

您可以假设我是32位整数(但16位还可以).如果是这样，则值i的范围为1 <= i <= 2^31-1.

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.

推荐答案

假设您有一个二进制补码i:

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

0b1101001010000000

，而您想找到-i.好吧，-i是i + (-i) == 0这样的数字.那那个财产有多少呢?好吧，如果您构造另一个数字:

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

，以便最右边的设置位与i中的相同，此后的所有位均为0，而此之前的所有位均与i中的位相反:

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

然后将这些数字加在一起时，进位沿数字左侧传播，只保留所有0位，因此为-i.

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.

现在，如果我们&这些数字，我们将得到什么?好吧，尾随零&一起产生零.左边的位在i和-i中是相反的，因此它们&一起产生零.但是，在i和-i中，最右边的设置位是1，所以这是i & -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

这篇关于为什么要进行位操作(-i)等于最右边的位?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！