popcount或者hamming weight（二进制1的个数问题）

第一次写关于算法的问题。今天数据库课老师在讲数据库底层实现的时候提到了位图索引，最后归结为1的个数，以前看到很多次关于1的个数的计算，今天总结一下。

最开始是有《编程之美》里面的问题引出的：如何最快地读取到二进制中1的个数. 最开始我也是感觉一个个地数不就完了，但是人家说了要求最快。一个个的数是O(N)级的。

1. 比如：int count=0;

for(;x;x>>1)

{

count++;

}//当然也有每次用x直接除以2 的。

2.后来就是用x&(x-1)的结果是否为0来判断，如果为零，有一个1，否则没有。

所以有：

for(;x;count++)

x&=x-1;

3.查表大法，就是一一列举这n位二进制所有的可能到数组中，然后直接查表就是了，这里就不赘述了

4.这个新的方法叫shift and add,正如名字一样，该算法用的就是shift 和add（移位和加法）：

对于n位二进制数，最多有n个1，而n必定能由n位二进制数来表示，因此我们在求出某k位中1的个数后，可以将结果直接存储在这k位中，不需要额外的空间。
以4位二进制数abcd为例，最终结果是a+b+c+d，循环的话需要4步加法

那么我们让abcd相邻的两个数相加，也就是 a+b+c+d=[a+b]+[c+d]

[0 b 0 d]

[0 a 0 c]

--------

[e f] [ g h]

ef=a+b   gh=c+d 而 0b0d=(abcd)&0101,0a0c=(abcd)>>1 &0101

[ef]  [gh]再相邻的两组相加

[00 ef]

    [gh]

--------

i j k l

ijkl=ef+gh  gh=(efgh)&& 0011 ,ef=(efgh)>>2 & 0011

依次入次递推。需要log(N)次

代码如下：

typedef unsigned __int64 uint64; //assume this gives 64-bits
const uint64 m1 = 0x5555555555555555; //binary: 0101...
const uint64 m2 = 0x3333333333333333; //binary: 00110011..
const uint64 m4 = 0x0f0f0f0f0f0f0f0f; //binary: 4 zeros, 4 ones ...
const uint64 m8 = 0x00ff00ff00ff00ff; //binary: 8 zeros, 8 ones ...
const uint64 m16 = 0x0000ffff0000ffff; //binary: 16 zeros, 16 ones ...
const uint64 m32 = 0x00000000ffffffff; //binary: 32 zeros, 32 ones
 
int popcount_1(uint64 x) {
 x = (x & m1 ) + ((x >> 1) & m1 ); 
 x = (x & m2 ) + ((x >> 2) & m2 ); 
 x = (x & m4 ) + ((x >> 4) & m4 ); 
 x = (x & m8 ) + ((x >> 8) & m8 ); 
 x = (x & m16) + ((x >> 16) & m16); 
 x = (x & m32) + ((x >> 32) & m32); 
 return x;
}

5.对shift and add的优化：

看到有三种优化，这里只提两种吧

 

1

int popcount_2(uint64 x)
{
    x -= (x >> 1) & m1;
    x = (x & m2) + ((x >> 2) & m2);
    x = (x + (x >> 4)) & m4;
    x += x >> 8;
    x += x >> 16;
    x += x >> 32;
    return x & 0x7f;

}

2.

int popcount_3(uint64 x) {
    x -= (x >> 1) & m1;
    x = (x & m2) + ((x >> 2) & m2);
    x = (x + (x >> 4)) & m4;
    return (x * h01)>>56;

据说这可是MIT的牛人想出来的高招(当时是求余，现在换成除法了更快）

我也是参见了wikipedia(但是看不懂）和http://blog.ibread.net/375/pop-count-problem/上面的文章。

int popcount_3(uint64 x) {
    x -= (x >> 1) & m1;
    x = (x & m2) + ((x >> 2) & m2);
    x = (x + (x >> 4)) & m4;
    return (x * h01)>>56;