<分区>
Possible Duplicate:
n & (n-1) what does this expression do?
考虑以下算法:
int count(int num)
{
int ones = 0;
while(num)
{
++ones;
num &= num - 1;
}
return ones;
}
num & (num-1)有什么意义？它是如何工作的？
<分区>
Possible Duplicate:
n & (n-1) what does this expression do?
考虑以下算法:
int count(int num)
{
int ones = 0;
while(num)
{
++ones;
num &= num - 1;
}
return ones;
}
num & (num-1)有什么意义？它是如何工作的？
最佳答案
num &= num - 1;
清除 num 中设置的最低有效位。
该算法通过清除它们并递增计数器直到它们全部消失来对设置的位进行计数。
要理解为什么它会清除最低有效位，您需要考虑递减对这些位的作用，当然还要理解 & 操作的作用。
二进制减法就像我们小时候教的十进制一样。 您从右(最低有效位)到左工作，尽可能简单地减去单个数字，并在必要时从下一个数字“借用”。
当从以一组零结尾的二进制数中减 1 时，这种“借用”和减法会将比最右边的 1 低位的所有零变为 1，并将最右边的 1 变为零(因为它是借来的) .
然后应用 & 运算符将所有较小的数字保留为零，因为它们在 num 中为零，并设置 num 的最低有效位> 为零，因为它在 num-1 中为零。
这两个操作都保持较高有效数字不变。
这是一个很好的列表 bit twiddling hacks包括这个，这是由于 Brian Kernighan .
关于c - 这个方法如何统计二进制表示中的1个数？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/11810507/