一道简单的算法题

题目：统计给定数字中，值为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^3	10^4	10^5	10^6	10^7	10^8
遍历	1	2	26	255	2700	29447
遍历（改进）	0	1	7	74	739	8046
查表	0	0	2	21	202	2166
SWAR	0	0	2	19	190	1876

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

参考资料：

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

from: http://www.jianshu.com/p/34fd5d477826?hmsr=toutiao.io&utm_medium=toutiao.io&utm_source=toutiao.io

秒客网