为什么位运算 i & (-i) 等于最右边的位？

Question

我学习了 Fenwick Tree 算法，上面写着“i & (-i) 等于最右边的位”。
例如，3 & (-3) = 1, 48 & (-48) = 16.。

我测试了 的结果i <= 64，所有值都满足条件。
但我不知道为什么所有正整数 i 的条件都满足（证明）。

请告诉我如何证明。

编辑：您可以假设 i 是 32 位整数（但 16 位也可以）。如果是，则 i 的取值范围为1 <= i <= 2^31-1。

Answer 1

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

0b1101001010000000

并且您想找到-i. 那么，-i是这样的数字吗i + (-i) == 0？那么这个属性是多少呢？好吧，如果你构造另一个数字：

 i: 0b1101001010000000
-i: 0b0010110110000000

这样最右边的设置位与 in 相同i，之后的所有位都是0，之前的所有位都是 in 的倒数i：

 i: 0b11010010 1 0000000
-i: 0b00101101 1 0000000

然后当你把这些数字加在一起时，进位从数字的左侧传播，只留下所有 0 位，所以这是-i.

现在，如果我们得到&这些数字，我们会得到什么？那么，尾随零&一起产生零。左边的位在iand 中是相反的-i，所以它们&一起产生零。但是最右边的设置位1在i和 中-i，所以这是 中唯一的设置位i & -i。

     i: 0b11010010 1 0000000
    -i: 0b00101101 1 0000000
i & -i: 0b00000000 1 0000000