Count Bits

Mon ,Jan 22 ,2018

在刷算法的时候遇到了好几个有趣的计算一个数中，bit位为1的个数。

1.直接计算

直接计算移位计算1.需要注意的是，输入参数。int 与 uint 的移位策略是不一样的。
int count(uint64 x)
{
    int count = 0;
    for(; x; x>>1)
        ++count;
    return count;
}

2.一点点小技巧

利用（8）1000 - 1 = （7）0111.

int count(uint64 x)
{
    int count = 0;
    for (; x; ++count)
        x&=x-1;
    return count;
}

3.分治

const uint64 m1  = 0x5555555555555555;
const uint64 m2  = 0x3333333333333333;
const uint64 m4  = 0x0f0f0f0f0f0f0f0f;
const uint64 m8  = 0x00ff00ff00ff00ff;
const uint64 m16 = 0x0000ffff0000ffff;
const uint64 m32 = 0x00000000ffffffff;

int count(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;
}

4.优化后的分治

int count(uint64 x) {
    x -= (x >> 1) & m1;              // 2 * a + b - a = a + b
    x = (x & m2) + ((x >> 2) & m2);  // 10 + 10 = 100 因此，会产生进位，所以为进位做好准备。
    x = (x + (x >> 4)) & m4;         // 最大是 0100 0100 = 1000 不会进位，因此可以先做加法再做与。
    x += x >>  8;                    // 不做与 运算。8位 已经表示 256, 
                                    // 在8位相加时，正确的和已经加在后8位了，前8位与后8位互不影响。
    x += x >> 16; 
    x += x >> 32;  
    return x & 0x7f;
}

5.再次优化

int count(uint64 x) {
    x -= (x >> 1) & m1;  
    x = (x & m2) + ((x >> 2) & m2);
    x = (x + (x >> 4)) & m4;    
    return (x * h01)>>56;   // 神来之笔
}

Diamondu

Count Bits