问题：
对于任意的非负整数，统计其二进制展开中数位1的总数。
解决:
在看这篇之前可以先看看上述这篇，这篇主要讨论其优化问题。
常规解法：
O(logn)：
无非就是每次取其二进制展开最后一位，是1就计数。
效率由位运算可知（右移一位等价于除以2），为 O(logn)。
优化解法1：
O(countOnes(n))：
解释如下：
优化解法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)。
为了理解起来方便，代码可简化为：
其他的一些有助于理解的解释有：
说简单点，就是一个 错位分段相加，然后递归合并的过程 。
下面是细节分析：
首先先看看那些诡异的数字都有什么特点：
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的个数。
例子，若求156中1的个数，156二进制是10011100
最终：
[1][0][0][1][1][1][0][0] //初始，每一位是一组
|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的个数
Original: https://www.cnblogs.com/ygsworld/p/11486638.html
Author: 回忆酿的甜
Title: 【转】对于任意的非负整数，统计其二进制展开中数位1的总数
原创文章受到原创版权保护。转载请注明出处：https://www.johngo689.com/582127/
转载文章受原作者版权保护。转载请注明原作者出处！