学步园

     给定一个数字求该数字二进制中1的个数被广泛应用于simhash中，求两个hash值得相似程度可以先将两个hash值做异或操作，然后统计异或结果二进制中1的个数来判断两个hash值得相似性。

    言归正传，求数字二进制中1的位数最直观的解法为所求数字不断的向右移位>>直到为0，统计移位过程中最低位是否是1，这样需要移位32~64位，代码如下：

int bitcout1(uint32_t num){
        int c = 0;
        while(num > 0){
                if(num & 0x1 == 1){
                        c++;
                }
                num >>= 1;
        }
        return c;
}

这种方式直观便于理解，但效率一般，对位运算比较熟悉的同学可能会发现数字减一后会将被减数的二进制中最后一个1变为0，例如7（111）-1 = 6（110），而7和6进行与操作就会将最后的1消除，利用这个原理我们可以这样处理1位数的问题。

int bitcount2(uint32_t num){
        int c = 0;
        for(c = 0; num; c++){
                num &= (num -1);
        }
        return c;
}

算法的复杂度只与数字二进制中1的个数相关，另外在空间复杂度允许的情况下可以直接采用查表法的方式进行计算，这样效率很高

unsigned int table[256] =
    {
        0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4,
        1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
        1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
        2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
        1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
        2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
        2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
        3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
        1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
        2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
        2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
        3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
        2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
        3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
        3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
        4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8,
    };
int bitcount7(unsigned int n)
{

    return table[n & 0xff] +
        table[(n >> 8) & 0xff] +
        table[(n >> 16) & 0xff] +
        table[(n >> 24) & 0xff] ;
}

这样的效率是最高的，只不过需要占用一定的空间