对人口计数算法有所了解 [英] Cast some light on population count algorithm

问题描述

我正在寻找执行popcount(设置位数的计数)的好方法.我在这里找到了这个

I looked for good methods to do popcount (count of set bits). I found this one, here

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
}

尝试一些示例，这确实是可行的.二进制运算/表示形式的什么属性使其可以工作?

Trying on a few examples, its true that it works. What property of binary operations / representation makes it work?

您能否暗示有关Popcount和二进制表示形式的进一步阅读?

Could you hint at some further readings on popcount and binary representation?

推荐答案

您首先要设置的初始v最初具有n位.

You're starting off with an initial v that initially has n bits in it set.

游戏的重点是在循环的每次迭代中少计算1位.这样，我们就可以计算出到达n = 0才能确定初始n值之前必须进行的循环迭代次数.

The point of the game is to have 1 less bit to count at each iteration of the loop. That way, we can just count the number of iterations of the loop that were necessary before we got to the point where n = 0 to figure out the value of the initial n.

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

Notice that, if n = 0, then v = 0, and so the loop will stop at this point. But so long as v > 0, we'll run the body of the loop at least once. At each iteration, we end up with a v that has 1 fewer bit set.

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

Here's why. The first property we need is that v && v == v. Now v is a sequence of bits (the exact number of bits depends on your machine / OS), that you can order from most significant to least significant. When you decrement v, we can note the following:

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

1. the least significant bit, call it v[k], that is set to 1 will be set to 0;
2. all bits more significant than v[k] will not change when you decrement v.

因此，以递减的方式与v进行AND运算将保留所有较高位，但将v [k]设置为0.根据定义，所有比v [k]低的位，即v [k- 1] ... v [0]已经为0，因为v [k]是最低有效位，为1".因此，与运算后，所有较低的有效位都将保持为0.结果是v && (v - 1)包含的设置为1的位要比v少一位.

Therefore, ANDing v with its decrement will preserve all the more significant bits, but set v[k] to 0. And by definition, all bits that are less significant than v[k], ie v[k-1] ... v[0], are already 0 because v[k] is "the least significant bit that is 1". Therefore after ANDing all the less significant bits will remain at 0. The upshot is that v && (v - 1) contains one less bit set to 1 than v has.

这篇关于对人口计数算法有所了解的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！