【转】对于任意的非负整数，统计其二进制展开中数位1的总数

转自 ：

问题：

　　对于任意的非负整数，统计其二进制展开中数位1的总数。

解决:

　　相关Blog：http://www.cnblogs.com/maples7/p/4324844.html

　　在看这篇之前可以先看看上述这篇，这篇主要讨论其优化问题。

常规解法：

O(logn)：

 1 int countOnes(unsigned int n)
 2 {
 3     int ones = 0;
 4     while (0 < n)
 5     {
 6         ones += (1 & n);
 7         n >>= 1;
 8     }
 9     return ones;
10 }

无非就是每次取其二进制展开最后一位，是1就计数。

效率由位运算可知（右移一位等价于除以2），为 O(logn)。

优化解法1：

O(countOnes(n))：

 1 int countOnes1(unsigned int n)
 2 {
 3     int ones = 0;
 4     while (0 < n)
 5     {
 6         ones++;            // 计数（最后至少有一位为1）
 7         n &= n - 1;        // 清除当前最靠右的1
 8     }
 9     return ones;
10 }

解释如下：

优化解法2：

O(logW), W = O(logn) 为整数的位宽, 实际上就是 O(1) 的算法。

代码及解释：

这个算法是一种合并计数器的策略。把输入数的32Bit当作32个计数器，代表每一位的1个数。然后合并相邻的2个“计数器”，使i成为16个计数器，每个计数器的值就是这2个Bit的1的个数；继续合并相邻的2个“计数器“，使i成为8个计数器，每个计数器的值就是4个Bit的1的个数。。依次类推，直到将i变成一个计数器，那么它的值就是32Bit的i中值为1的Bit的个数。

实际上还是二分的思想，把一位一位计数变成二分的计数，使 O(logn) 变成了 O(loglogn)。

为了理解起来方便，代码可简化为：

 1 int BitCount4(unsigned int n) 
 2 { 
 3     n = (n &0x55555555) + ((n >>1) &0x55555555) ; 
 4     n = (n &0x33333333) + ((n >>2) &0x33333333) ; 
 5     n = (n &0x0f0f0f0f) + ((n >>4) &0x0f0f0f0f) ; 
 6     n = (n &0x00ff00ff) + ((n >>8) &0x00ff00ff) ; 
 7     n = (n &0x0000ffff) + ((n >>16) &0x0000ffff) ; 
 8 
 9     return n ; 
10 }

其他的一些有助于理解的解释有：

本段讲解来源:http://www.sandy-sp.com/blog/article.asp?id=11

说简单点，就是一个 错位分段相加，然后递归合并的过程 。

下面是细节分析：

首先先看看那些诡异的数字都有什么特点：
0x5555……这个换成二进制之后就是0101010101010101……
0x3333……这个换成二进制之后就是0011001100110011……
0x0f0f……...这个换成二进制之后就是0000111100001111……
看出来点什么了吗？
如果把这些二进制序列看作一个循环的周期序列的话，

那么第一个序列的周期是2，每个周期是01，第二个序列的周期是4，每个周期是0011，第三个的周期是8，每个是00001111……

这样的话，我们可以看看如果一个数和这些玩意相与之后的结果：

整个数按照上述的周期被分成了n段，每段里面的前半截都被清零，后半截保留了数据。不同在于这些数分段的长度是2倍增长的。于是我们可以姑且命名它们为“分段截取常数”。

这样，如果我们按照分段的思想，每个周期分成一段的话，你或许就可以感觉到这个分段是二分法的倒过来——类似二段合并一样的东西！


现 在回头来看问题，我们要求的是1的个数。这就要有一个清点并相加的过程（查表法除外）。使用&运算和移位运算可以帮我们找到1，但是却无法计算1 的个数，需要由加法来完成。最传统的逐位查找并相加，每次只加了1位，显然比较浪费，我们能否一次用加法来计算多次的位数呢？

再考虑问题，找到了1的位置，如何把这个位置变成数量。最简单的情况，一个2位的数，比如11，只要把它的第二位和第一位相加，不就得到了1的个数了吗？！所以对于2位的x，有x中1的个数=(x>>1)+(x&1)。是不是和上面的式子有点像？

再考虑稍复杂的，一个字节内的情况。
一个字节的x，显然不能用(x>>1)+(x&1)的方法来完成，但是我们受到了启发，如果把x分段相加呢？把x分成4个2位的段，然后相加，就会产生4个2位的数，每个都代表了x对应2位地方的1的个数。

（来源：http://www.sandy-sp.com/blog/article.asp?id=11）

例子，若求156中1的个数，156二进制是10011100
最终：

[1][0][0][1][1][1][0][0] //初始，每一位是一组
---
|0  0 |0  1 |0  1 |0  0|  //与01010101相与的结果，同时2个一组分组
+
|0  1 |0  0 |0  1 |0  0|  //右移一位后与01010101相与的结果
=
[0  1][0  1][1  0][0  0]  //相加完毕后，现在每2位是一组，每一组保存的都是最初在这2位的1的个数
----
|0  0  0  1 |0  0  0  0|  //与00110011相与的结果，4个一组分组
+
|0  0  0  1 |0  0  1  0|  //右移两位后与00110011相与的结果
=
[0  0  1  0][0  0  1  0] //相加完毕后，现在每4位是一组，并且每组保存的都是最初这4位的1的个数
----
|0  0  0  0  0  0  1  0|
+
|0  0  0  0  0  0  1  0|
=
[0  0  0  0  0  1  0  0] //最终合并为8位1组，保存的是整个数中1的个数，即4。

（来源：http://www.cnblogs.com/xianghang123/archive/2011/08/24/2152408.html）

比如这个例子，143的二进制表示是10001111，这里只有8位，高位的0怎么进行与的位运算也是0，所以只考虑低位的运算，按照这个算法走一次

+---+---+---+---+---+---+---+---+
| 1 | 0 | 0 | 0 | 1 | 1 | 1 | 1 |   <---143
+---+---+---+---+---+---+---+---+
|  0 1  |  0 0  |  1 0  |  1 0  |   <---第一次运算后
+-------+-------+-------+-------+
|    0 0 0 1    |    0 1 0 0    |   <---第二次运算后
+---------------+---------------+
|        0 0 0 0 0 1 0 1        |   <---第三次运算后，得数为5
+-------------------------------+

这里运用了分治的思想，先计算每对相邻的2位中有几个1，再计算每相邻的4位中有几个1，下来8位，16位，32位，因为2^5＝32，所以对于32位的机器，5条位运算语句就够了。

像这里第二行第一个格子中，01就表示前两位有1个1，00表示下来的两位中没有1，其实同理。再下来01+00=0001表示前四位中有1个1，同样的10+10=0100表示低四位中有4个1，最后一步0001+0100=00000101表示整个8位中有5个1。

《数据结构习题解析》，邓俊辉

Reference：

1、http://blog.chinaunix.net/uid-21275705-id-224360.html

2、http://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetNaive

3、http://www.cnblogs.com/graphics/archive/2010/06/21/1752421.html