3

我寻找了做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和二进制表示的进一步阅读吗？

4

2 回答 2

4

您从一个初始设置开始，该初始v设置最初包含 n 位。

游戏的重点是在循环的每次迭代中减少 1 位要计数。这样，我们可以只计算在达到 n = 0 的点之前所需的循环迭代次数来计算初始 n 的值。

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

这就是为什么。我们需要的第一个属性是v && v == v. 现在v是一个位序列（确切的位数取决于您的机器/操作系统），您可以从最高位到最低位进行排序。当您递减 时v，我们可以注意到以下内容：

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

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

于 2012-10-01T18:39:00.340 回答
0

1从一个位中减去一个0位会将该位变为 a1并导致从左边的下一位借位，从而也导致1那里的减法。这继续向左级联，直到您到达一点，从1那里减去is 。至此减法完成。您已将所有转换为第一个设置位，并将该位从转换为.1100110

当您and使用之前和之后的值时，before第一个位的右侧after为零，并且该位的该位为零。由于任何与零相加的东西都是零，因此您保留原始值中的所有零并将单个位也设置为零。

于 2012-10-01T19:26:54.133 回答