在32位计数设置位的方法的说明
这个问题在这里已经有了答案：
它的工作原理是，你可以通过分成两半来计算所设置位的总数，计算两个半部分中设置位的数量，然后将它们相加。 也被称为Divide and Conquer范式。 让我们进入细节..
v = v - ((v >> 1) & 0x55555555);
位的两个比特的数目可以是0b00 ， 0b01或0b10 。 让我们试着去解决这个问题。
---------------------------------------------
| v | (v >> 1) & 0b1010 | v - x |
---------------------------------------------
0b00 0b00 0b00
0b01 0b00 0b01
0b10 0b01 0b01
0b11 0b01 0b10
这是所需要的，最后一列显示了每两个位对中设定位的计数。 如果这两个比特数>= 2 (0b10)然后and产生0b01 ，否则它产生0b00 。
v = (v & 0x33333333) + ((v >> 2) & 0x33333333);
这个陈述应该很容易理解。 在第一次操作后，我们每两位都有设定位数，现在我们每4位总结一次。
v & 0b11001100 //masks out even two bits
(v >> 2) & 0b11001100 // masks out odd two bits
然后我们总结上述结果，给我们设置4位的总位数。最后一条语句是最棘手的。
c = ((v + (v >> 4) & 0xF0F0F0F) * 0x1010101) >> 24;
让我们再来分析一下..
v + (v >> 4)
它与第二条语句相似，我们将数组中的位设为4组。 我们知道，由于我们以前的操作，每个半字节都有其中的设定位数。 让我们看一个例子，假设我们有字节0b01000010 。 这意味着第一个半字节设置为4位，第二个设置为2位。 现在我们将这些小节加在一起。
0b01000010 + 0b01000000
它给了我们在第一个半字节0b01100010中的一个字节中的设置位数，因此我们屏蔽了数字中所有字节的最后四个字节（丢弃它们）。
0b01100010 & 0xF0 = 0b01100000
现在每个字节都有设置位的数量。 我们需要将它们加在一起。 诀窍是把结果乘以0b10101010 ，这有一个有趣的属性。 如果我们的号码有四个字节ABCD ，它将产生一个带有这些字节A+B+C+D B+C+D C+DD的新号码。 一个4字节的数字最多可以设置32位，可以表示为0b00100000 。
我们现在需要的是第一个字节，它具有所有字节中所有设置位的总和，我们可以通过>> 24得到它。 该算法是为32 bit字设计的，但可以轻松修改为64 bit字。
关于汉明重量的维基百科文章有至少有文件记载的代码，并且从更一般的概念构建了超快速12版本。
//This uses fewer arithmetic operations than any other known
//implementation on machines with fast multiplication.
//It uses 12 arithmetic operations, one of which is a multiply.
int popcount_3(uint64 x) {
x -= (x >> 1) & m1; //put count of each 2 bits into those 2 bits
x = (x & m2) + ((x >> 2) & m2); //put count of each 4 bits into those 4 bits
x = (x + (x >> 4)) & m4; //put count of each 8 bits into those 8 bits
return (x * h01)>>56; //returns left 8 bits of x + (x<<8) + (x<<16) + (x<<24) + ...
}
http://en.wikipedia.org/wiki/Hamming_weight
链接地址: http://www.djcxy.com/p/72603.html上一篇: Explanation of a method of counting set bits in a 32
下一篇: Count the number of bits set using only bitwise operations