c - 此方法如何计算二进制表示中 1 的数量？

Question

可能重复：
n & (n-1) 这个表达式有什么作用？

考虑以下算法：

int count(int num)
{
  int ones = 0;
  while(num)
  {
    ++ones; 
    num &= num - 1;
  }

  return ones;
}

有什么意义num & (num-1)？它是如何工作的？

score 7 · Accepted Answer

这是一个更详细（但写得不是很好！）的答案。

有两种情况：要么设置最低有效位，然后“num-1”取消设置它。或者未设置，则 num-1 将所有尾随零变为 1，将最低有效位 1 变为 0，其余位不变。当您“与”时，所有未更改的位都是相同的，与 0 相加的最低有效 1 变为 0，其他剩余位为零。这在此处进行了说明：

num             =      1000110111[1]0000
num - 1         =      1000110111[0]1111
num & (num - 1) =      1000110111[0]0000

我要指出的是，通常有一个组装操作来计算单个循环中的数量。该操作称为“popcount”，例如在 GCC 中，可以使用“__builtin_popcount”访问它，有关详细信息，请参阅此链接。

score 7 · Accepted Answer

num &= num - 1;

清除 num 中设置的最低有效位。

该算法通过清除它们并增加计数器直到它们全部消失来计算设置的位。

要了解为什么它会清除最低有效位，您需要考虑递减对位的作用，当然还要了解&操作的作用。

二进制减法就像我们小时候都用十进制教过的过程一样。您从右（最不重要）向左工作，尽可能简单地减去单个数字，并在必要时从下一个数字“借用”。

当从以一组零结尾的二进制数中减去 1 时，这种“借用”和减法会将比最右边的 1 更低位置的所有零变为 1，并将最右边的 1 变为零（因为它是借用的）。

然后应用&运算符将所有较小的数字保留为零，因为它们在中为零num，并将的最低有效位设置num为零，因为它在中为零num-1。

这两种操作都使较高的有效数字保持不变。

这是一个很好的小技巧列表，包括这个，这是由Brian Kernighan提供的。

score -1 · Accepted Answer

该算法像泵一样运行，有效地将“num”变量中的位移动到右侧。线

num &= num - 1;

是完成工作的地方，同时进行赋值和布尔 AND 操作。这都是关于位算术的。

绒球

3 回答 3