1

我看到了这段代码，叫做“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
}
4

3 回答 3

4

演练

让我们用一个例子来遍历循环：让我们设置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

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

当您在and之间进行按位与时，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，我们已经计算了所有位。

于 2020-01-09T23:49:11.650 回答
4

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

它的工作原理是：当你从一个数字中减去一个时，你将最低有效的一位更改为 0，将更不重要的位更改为 1——尽管这并不重要。没关系，因为它们在您要递减的值中为零，因此无论如何在与操作之后它们都将为零。

XXX1 => XXX0
XX10 => XX01
X100 => X011
etc.
于 2020-01-09T23:08:47.243 回答
3

让A=a n-1 a n-2 ...a 1 a 0是我们要计算位的数字，而k是最右边位的索引。

因此A=a n-1 a n-2 ...a k+1 100...0=Ak+2 k其中Ak=a n-1 a n-2 ...a k+1 000... 0

由于 2 k -1=000..0111..11，我们有 A-1=Ak+2 k -1=a n-1 a n-2 ...a k+1 011...11

现在执行A和A-1的按位 &

a n-1 a n-2 ...a k+1 100...0 A
a n-1 a n-2 ...a k+1 011...1 A-1
a n-1 a n -2 ...a k+1 000...0 A&A-1=Ak

所以A&A-1与A相同，只是它的最右边的位已被清除，这证明了该方法的有效性。

于 2020-01-10T07:54:14.973 回答