有人可以解释为什么这可以计算无符号整数中的设置位吗？

Question

我看到这段代码叫做 "Counting bits set, Brian Kernighan's way"。我对 "bitwise and'ing" 一个整数及其递减量如何计算设置位感到困惑，有人可以解释一下吗？

unsigned int v; // count the number of bits set in v
unsigned int c; // c accumulates the total bits set in v
for (c = 0; v; c++)
{
  v &= v - 1; // clear the least significant bit set
}

Answer 1

每次循环计数一位，并清除一位（设置为零）。

它的工作原理是：当您从数字中减去 1 时，您会将最低有效位更改为零，而将更不重要的位更改为 1 - 尽管这无关紧要。这无关紧要，因为它们在您要递减的值中为零，因此无论如何在与运算之后它们都会为零。

XXX1 => XXX0
XX10 => XX01
X100 => X011
etc.

Answer 2

演练

让我们通过一个例子来遍历循环：让我们设置 v = 42，即二进制的 0010 1010。

第一次迭代：c=0, v=42 (0010 1010)。现在 v-1 是 41 也就是 0010 1001 的二进制。让我们计算 v & v-1:
```
   0010 1010
 & 0010 1001
   .........
   0010 1000
```
现在 v&v-1 的二进制值为 0010 1000 或十进制为 40。此值存储到 v.
第二次迭代：c=1, v=40 (0010 1000)。现在 v-1 是 39 也就是 0010 0111 的二进制。让我们计算 v & v-1:
```
   0010 1000
 & 0010 0111
   .........
   0010 0000
```
现在 v&v-1 的值为 0010 0000，十进制为 32。此值存储到 v.
第三次迭代：c=2, v=32 (0010 0000)。现在 v-1 是 31 也就是 0001 1111 的二进制。让我们计算 v & v-1:
```
   0010 0000
 & 0001 1111
   .........
   0000 0000
```
现在v&v-1的值为0。
第四次迭代：c=3, v=0。 循环终止。 c 包含 3 这是 42.

为什么有效

您可以看到 v-1 的二进制表示将 最低有效位 或 LSB（即最右边的 1 位）从 1 设置为 0 并且LSB 右边从 0 到 1 的所有位。

当您在 v 和 v-1 之间执行 按位与 时，从 LSB 剩下的位在 v 和 v 中相同v-1 所以按位 AND 将使它们保持不变。 LSB 右侧的所有位（包括 LSB 本身）都不同，因此结果位将为 0。

在我们最初的 v=42 (0010 1010) 示例中，LSB 是从右边数第二位。您可以看到 v-1 与 42 具有相同的位，除了最后两个：0 变成了 1，1 变成了 0。

与 v=40 (0010 1000) 类似，LSB 是右起第四位。在计算v-1 (0010 0111)时可以看到，左边四位不变，右边四位倒转（0变成1，1变成0）。

因此v = v & v-1的作用是将v的最低有效位设置为0，其余保持不变。以这种方式清除所有位后，v 为 0，我们已对所有位进行计数。

Answer 3

令A=a_n-1a_n-2...a₁a₀ 是我们要计算位的数字，k 是右边的索引最多一位。

因此A=a_n-1a_n-2...a_k+1100...0=Ak+2^k 其中Ak=a_n-1a_n-2...a_k+1000...0

作为 2^k−1=000..0111..11，我们有 A-1=Ak+2^k-1=a_n-1a_n-2...a_k+1011...11

现在执行A和A-1

的按位&

a_n-1a_n-2...a_k+1100...0 A
a_n-1a_n-2...a_k+1 011...1A-1
a_n-1a_n-2...a_k+1 000...0 A&A-1=Ak

所以A&A-1等同于A，只是最右边的位被清零了，证明了方法。

有人可以解释为什么这可以计算无符号整数中的设置位吗？

Can someone explains why this works to count set bits in an unsigned integer?

c

bit-manipulation

kernighan-and-ritchie

演练

为什么有效