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

Question

可能重复:
n&(n-1)这个表达式做什么？

考虑以下算法:

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

  return ones;
}

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

Answer 1

num &= num - 1;

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

该算法通过清除它们并递增计数器来计算所设置的位,直到它们全部消失为止.

要理解为什么它清除了最低有效位,你需要考虑递减对位的作用,当然要理解&操作的作用.

在二进制中减去工作就像我们在十进制中作为孩子一样教导的过程.你从正确(最不重要)到左边工作,只要在可能的情况下减去个别数字,并在必要时从下一个数字"借用".

当从以一组零结尾的二进制数中减去1时,这种"借用"和减法将所有零都置于低于最右边1到1的位置,并将最右边的1变为零(因为它是借用的).

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

这两个操作都保持更高有效数字不变.

这里有一个很好的列表位摆弄黑客包括这一个,这是由于布赖恩Kernighan的.

Answer 2

这是一个更详细(但写得不太好)的答案.

有两种情况:设置最低有效位,然后"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

我想指出,通常有一个汇编操作来统计单个循环中的1个.该操作被称为"popcount",例如在GCC中,可以使用"__builtin_popcount"访问它,有关详细信息,请参阅此链接.