一道简单的算法题

2017-04-14 本文已影响644人 Torival

题目：统计给定数字中，值为1的二进制位的数量。如果是数组呢？

解法1：遍历算法

int getBitCount(unsigned int num) {
    int count = 0;
    
    while(num) {
        if(num & 0x01)
            count++;
        
        num = num >> 1;
    }
    
    return count;
}

第一种想法比较简单，从最后一位开始，比较是否为1，如果为1，就计数器加一。循环次数固定，32次。但是这种方法有一个地方需要注意，那就形参必须为unsigned int。否则，如果num为负数时，此时右移为了保证移位后还是负数，最高位会一直置为1，那将陷入死循环。

解法2：遍历算法（改进）

int getBitCount2(unsigned int num) {
    int count = 0;
    
    while(num) {
        count++;
        
        num = num & (num - 1);
    }
    
    return count;
}

相比较第一种算法，我们不必每次判断一位，而是通过num & （num-1）来判断。每次&之后，可以把num最低位的1置为0，那么循环的次数，也就降低到了所含1的个数。

解法3：查表法

static const unsigned char bitsinbyte[256] = {
    //0000 0000 - 0000 0001
    0,1,
    
    //0000 0010 - 0000 0011
    1,2,
    
    //0000 0100 - 0000 0111
    1,2,2,3,
    
    //0000 1000 - 0000 1111
    1,2,2,3,2,3,3,4,
    
    //0001 0000 - 0001 1111
    1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,
    
    //0010 0000 - 0011 1111
    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,
    
    //0100 0000 - 0111 1111
    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,
    
    //1000 0000 - 1111 1111
    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 getBitCount3(unsigned int num) {
    unsigned char n1 = num;
    unsigned char n2 = num >> 8;
    unsigned char n3 = num >> 16;
    unsigned char n4 = num >> 24;
    
    return bitsinbyte[n1] + bitsinbyte[n2] +
        bitsinbyte[n3] + bitsinbyte[n4];
}

通过定义一个bitsinbyte[256]字节数组，里面存放0000 0000 - 1111 1111不同数字的1的个数。然后把需要统计的数字划分为四段，然后分部计算。

解法4：variable-precision SWAR算法

unsigned int getBitCount4(unsigned int num) {
    num = (num & 0x55555555) + ((num >> 1) & 0x55555555);
    
    num = (num & 0x33333333) + ((num >> 2) & 0x33333333);
    
    num = (num & 0x0F0F0F0F) + ((num >> 4) & 0x0F0F0F0F);
    
    num = (num * 0x01010101 >> 24);
    
    return num;
}

这种算法也常被称为汉明重量（Hamming Weight），通过一系列的位移和位运算操作，可以在常数时间内计算多个字节的汉明重量，而且不需要使用额外的内存。接下来分析以下这个算法。

为了方便描述，我们假定一个字节0xD8 ->(二进制) 0B11011000从后往前，依次为1到8位，第一位为0，第八位为1。

step1：首先我们可以很容易的知道，0x55555555对应的二进制的数为0B 01010101 01010101 01010101 01010101，而第一步运算相当于，把num奇偶位的数字进行相加。并且存放在了奇数位，相加如有进位则放在偶数位。
step2：0x33333333对应的二进制的数为0B 00110011 00110011 00110011 00110011，把num的奇数位，与下一个奇数位相加（第一位加第三位，第五位加第七位），把num的偶数位，与下一个偶数位相加（第二位加第四位，第六位加第八位）。如有进位，则保存到第三位，或者第七位。
step3：0x0F0F0F0F对应的二进制的数为0B 00001111 00001111 00001111 00001111，把num的每个字节中，前四位，与后四位相加。此时，每个字节中所含1的个数，都集中到了前四位。此时可以用0x0m0n0i0j来表示这个数，其中m，n，i，j代表之前num每个字节所含1的个数。
step4：也是最神奇的一步，通过这一步，把m，n，i，j这四个数相加。得到最终的个数。在这一步，我们不需要把0x01010101化为二进制。而是直接带入运算。通过下面的计算式，我们可以看出相乘，然后右移24位，刚好就是我们所要的结果。神奇~

magic.png

运算速度

|算法(ms)/数据级别| 10| 10^2| 10^3| 10^4| 10^5| 10^6| 10^7| 10^8|
| :----:| :----: | :----: | :----: | :----: | :----: | :----: | :----: |
|遍历|0 |0 |1 |2 |26| 255 |2700 |29447|
|遍历（改进）|0 |0 |0 |1 |7 |74 |739 |8046|
|查表|0 |0 |0 |0 |2 |21 |202 |2166|
|SWAR|0 |0 |0 |0 |2 |19 |190 |1876|

以上是模拟不同的数据级别，运行测试的结果。

参考资料：

http://stackoverflow.com/questions/109023/how-to-count-the-number-of-set-bits-in-a-32-bit-integer
<<剑指offer>> 第十题
<<redis设计与实现>> 第22章，BITCOUNT实现
测试代码