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

Question

我看到了这段名为“Counting bits set, Brian Kernighan's way”的代码。我很困惑如何“按位与”整数及其减量如何计算设置位，有人可以解释一下吗？

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

演练

让我们用一个例子来演示一下循环：让我们设置二进制v = 42 形式0010 1010。

• 第一次迭代：c=0, v=42 (0010 1010). 现在v-1 是41 二进制0010 1001的。我们来计算一下v & v-1：

     0010 1010
   & 0010 1001
     .........
     0010 1000
  

  Nowv&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。

为什么它有效

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

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

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

同样，v=40 (0010 1000)LSB 是右起第四位。计算时，v-1 (0010 0111)您可以看到左侧四位保持不变，而右侧四位反转（零变为一，一变为零）。

因此，的效果v = v & v-1是将 的最低有效位设置v为 0，其余部分保持不变。当所有位都以这种方式清除后，v为 0，我们就已经计算了所有位。