c++ - 计算位数：这条线是如何工作的？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;
}

有人可以简单地向我解释一下或给出一些“证据”吗？

Answer 1

任何无符号整数 'n' 将具有以下最后 k 位： 1 后跟 (k-1) 个零：100...0 请注意，k 可以为 1，在这种情况下没有零。

(n - 1) 将以这种格式结束：0 后跟 (k-1) 1：011...1

因此，n & (n-1) 将以“k”个零结尾：100...0 & 011...1 = 000...0

因此 n & (n - 1) 将消除最右边的“1”。每次迭代基本上都会删除最右边的“1”数字，因此您可以计算 1 的数量。

Answer 2

我一直在复习位操作并遇到了这个问题。现在（3年后）可能对原始海报没有用处，但无论如何我都会回答以提高其他观众的质量。

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

我们应该确保我们知道这一点，因为这是打破循环的唯一方法（n != 0）。比方说n=8。位表示将是00001000. n-1（或 7）的位表示为00000111. &运算符返回两个参数中设置的位。由于00001000并且00000111没有设置任何类似的位，因此结果将是00000000（或零）。您可能已经注意到数字 8 不是随机选择的。这是 2 的幂的示例n。所有 2 的幂（2、4、8、16 等）都将产生相同的结果。

当你传递一个不是 2 的指数的东西时会发生什么？例如，当 时n=6，位表示是00000110andn-1=5或00000101.The&应用于这 2 个参数，它们只有一个共同的位，即 4。现在，n=4它不是零，所以我们递增c并尝试与 相同的过程n=4。正如我们在上面看到的，4 是 2 的指数，因此它将在下一次比较中打破循环。它正在切断最右边的位，直到n等于 2 的幂。

是什么c？

它仅在每个循环中递增 1 并从 0 开始。c是在数字等于 2 的幂之前被切断的位数。