binary - 对人口计数算法有所了解

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，我们就会至少运行一次循环体。在每次迭代中，我们最终得到一个少了 1 个位集的 v。

原因如下。我们需要的第一个属性是 v && v == v。现在 v 是一个位序列(确切的位数取决于您的机器/操作系统)，您可以从最高有效位到最低有效位排序。当您递减 v 时，我们可以注意到以下几点:

1. 最低有效位，称为v[k]，设置为1将设置为0；
2. 当您递减 v 时，所有比 v[k] 更重要的位不会改变。

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