计算位数：这行代码是如何工作的？ n=n&(n-1);

Question

我需要一些解释，说明这行代码是如何工作的。
我知道这个函数计算二进制中1的位数，但是这行代码如何清除最右边的1位呢？

int f(int n) {
    int c;
    for (c = 0; n != 0; ++c) 
        n = n & (n - 1);
    return c;
}

有人能简要地解释一下吗或者提供一些“证明”吗？

- BBLN

---

考虑长减法和“借位”。 - Ben Voigt

它会清除最右边的位，因为 n-1 的最右边一位永远不会和 n 的最右边一位相同。 - David G

肯尼汉的位计数技巧！（http://cs.stanford.edu/~seander/bithacks.html#CountBitsSetKernighan） - Ternary

位操作技巧通常应使用无符号类型进行，以防您的计算机对有符号类型不使用二进制补码（或者编译器尝试根据标准不要求有符号类型使用二进制补码的知识进行一些聪明的优化）。 - Adrian McCarthy

这个问题询问的是 n = n & (n - 1)，换句话说就是 n &= (n-1)。建议的“已回答”问题要求另外一件事情，正如标题所述：n & (n-1) 是做什么的。前者的目的是移除最右边的值为1的位，而后者则是检查n是否为2的幂。我可以看出这两个表达式看起来相似，它们的真值表也相同，但这两个问题和因此得出的答案无疑是不同的。 - F.S.

Answer 1

任何无符号整数'n'的最后'k'位数字如下: 一个后面跟着(k-1)个零：100...0 注意，当k为1时没有零。

(n-1)以以下格式结束: 零，后面跟着(k-1)个1: 011...1

n & (n-1) 将以'k'个零结尾：100...0 & 011...1 = 000...0 因此，n & (n-1) 将消除最右边的 '1'。 每次迭代都将删除最右边的 '1' 数字，因此您可以计算1的数量。

- user1952500

---

如果平台使用的是有符号幅值表示法而不是二进制补码，那么这是否适用于负值？ - Adrian McCarthy

Answer 2

我一直在学习位运算，偶然发现了这个问题。虽然原帖已经三年过去，对楼主可能没有用处了，但我还是要回答，以提高其他观众的质量。

n & (n-1) 等于零是什么意思？

我们应该确保了解这一点，因为它是打破循环(n != 0)的唯一方法。比如说，n=8。其二进制表示为00001000。而 n-1 (或7) 的二进制表示为00000111。& 运算符返回两个参数中设置的位。由于00001000和00000111没有任何相似的位被设置，结果将是00000000(或零)。 你可能会发现，数字8并不是随机选择的。这是一个例子，其中 n 是2的幂。所有的2的幂(2、4、8、16等)将具有相同的结果。

当你传递的不是2的幂时会发生什么呢？例如，当n=6时，二进制表示为00000110，n-1=5或00000101。& 运算应用于这两个参数，它们只有一个相同的位，即4. 现在，n=4，不为零，所以我们增加 c 并尝试使用 n=4 重复相同的过程。如上所述，4是2的幂，因此它将在下一个比较中打破循环。它会一直去掉最右边的位，直到 n 等于2的幂。

c 是什么？

c仅每次循环递增一次，并从0开始。 c 是在数字等于2的幂之前切掉的位数。

- Andrew Campbell