algorithm - 为什么 n 按位和 -n 总是返回最右边的位(最后一位)

Question

这是 python 代码片段:

1 & -1 # 1
2 & -2 # 2
3 & -3 # 1
...

似乎任何 n & -n 总是返回最右边的(最后)位，我真的不知道为什么。有人可以帮助我理解这一点吗？

Answer 1

这是由于负数用二进制表示的方式，称为二进制补码表示。

创建某个数字 n 的二进制补码(换句话说，创建 -n 的表示):

• 反转所有位
• 加1

换句话说，当您编写 1 & -1 时，它实际上意味着 1 & ((~1)+1)。初始 ~1 给出值 1111110，加一给出 11111111。 (对于这些示例，我们坚持使用 8 位。)将这些值与 1 进行 AND 运算只会得到 1。

在下一种情况下，2 & -2 表示 2 & ((~2)+1)。反转 2 得到 11111101，加一得到 11111110。然后与 2(10 二进制)AND 得到 2。

最后 3 & -3 表示 3 & ((~3)+1)。反转 3 得到 11111100，添加 1 得到 11111101，并且与 3 ( 11 二进制)给出 1。