让我们了解一下人口统计算法

Question

我寻找了做popcount (设置位计数)的好方法。我找到了这个，这里

http://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetKernighan

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
}

试着举几个例子，它确实是有效的。二进制操作/表示的什么属性使其工作？

你能提示一下关于popcount和二进制表示的一些进一步的读数吗？

Answer 1

您从一个初始v开始，它最初设置了n位。

游戏的要点是在循环的每次迭代中少计算1个比特。这样，我们就可以计算循环的迭代次数，在我们到达n =0的点之前，我们可以计算出初始n的值。

请注意，如果n= 0，则v= 0，因此循环将在此处停止。但只要v> 0，我们就至少运行一次循环体。在每次迭代中，我们最终得到一个v，它具有更少的1位集。

这就是为什么。我们需要的第一个属性是v && v == v。现在，v是一个位序列(确切的位数取决于您的机器/ OS)，您可以从最高有效位到最低有效位排序。当您递减v时，我们可以注意到以下内容：

当您减少v.时，

1. 最低有效位，称为vk，设置为1将设置为0；
2. 所有比vk更重要的位将不会更改

因此，ANDing v及其减量将保留所有更高有效位，但将vk设置为0。根据定义，所有比vk重要的比特，即vk-1...v已经是0了，因为vk是“1的最低有效位”。因此，在ANDing之后，所有较低有效位将保持为0。结果是，与v相比，v && (v - 1)包含的设置为1的位少了一位。

Answer 2

从0位中减去1位会将该位转换为1，并导致从下一位向左借用，从而在那里也会产生减法1。这将继续向左进行级联，直到到达1位，其中从1中减去1为0。在这一点上，减法完成。您已经将第一个设置位之前的所有0转换为1，并将该位从1转换为0。

当您对before和after值执行and操作时，before在第一位的右侧为零，after在该位的位置为零。因为任何与零进行and运算的值都是零，所以您可以保留原始值中的所有零，并将单个位也设置为零。