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

Question

给定一个数字n，按位操作n & (n - 1)总是产生一个与n相差1位的数字>。以下是一些示例:

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) 总是从 n 中清除 1 位。为什么是这样？有人可以提供证明吗？

Answer 1

一些初步的评论:

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

当 n 为奇数时，减 1 很容易:您只需清除最后的 1 位即可。当n不为奇数时，你需要从相邻的位“借”，这会导致潜在的级联借位，直到你找到一个你可以借的1位(参见American method for manual在 Wikipedia 上减法)。这意味着从右边开始(在 n 的最低有效位)，您将一位一位地翻转，直到遇到第一个 1 位，它也被翻转。

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

由于对 n 的按位与运算将为为获得 n-1 而翻转的每一位生成 0，但会保留任何其他位n 和以前一样，它实际上清除了一个 n 的 1 位。

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