为什么 n & (n - 1) 总是从 n 中清除 1 位？

Question

给定一个数字n，逐位运算n & (n - 1)总是产生一个距离 1 位的数字n。以下是一些示例：

n = 4 => b'100' & b'011' = b'000'
n = 5 => b'101' & b'100' = b'100'
n = 6 => b'110' & b'101' = b'100' 

换句话说，n & (n - 1)总是从 中清除 1 位n。为什么是这样？有人可以提供证明吗？

Answer 1

一些初步评论：

• 当n非零时，该陈述成立。必须至少有一个 1 位。
• 按位 AND 运算复制两个操作数 (和) 中相同的位，并在相应位不同(和)时生成零位。1&1==10&0==01&0==00&1==0

当n为奇数时，减 1 很容易：您只需清除最后的 1 位即可。当n不是奇数时，您需要从相邻位“借用”，这会导致潜在的借用级联，直到找到可以借用的 1 位（请参阅维基百科上的美国手动减法方法）。这意味着从右侧开始（从n的最低有效位开始），逐个翻转位，直到遇到第一个 1 位，该位也被翻转。

因此，在减法中，您翻转一组位，其中恰好包含一个1 位，因此这是唯一一个翻转为 0 位的位。

由于对n进行按位 AND 运算将为得到n-1 的每一位翻转生成 0 ，但会保留n的任何其他位，因为它实际上清除了n的一个1 位。

由此还可以看出，被清除的位始终是n中最低有效的 1 位。