题目：统计给定数字中，值为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实现
- 测试代码
网友评论