面试中，除了TopK，是否被问过：求一个正整数的二进制表示包含多少个1？
画外音：姊妹篇《拜托，面试别再问我TopK了！！！》。
例如：
uint32_t i=58585858;
i的二进制表示是：
0000 0011 0111 1101 1111 0011 0000 0010
于是，i的二进制表示包含15个1。
到底有几种方法，这些思路里蕴含的优化思路究竟是怎么样的，今天和大家聊一聊。
一、位移法
思路：既然输入n是uint32，每次取n的最低位，判断是不是1，位移32次，循环判断即可。
伪代码：
do{
if ((n&1)==1){
result++;
}
n>>= 1;
i++;
} while(i<32);
分析：不管n的二进制表示里包含多少个1，都需要循环计算32次，比较耗时。有没有可能，每次消除掉一个1，这样来降低计算次数呢？
二、求与法
观察一下n与n-1这两个数的二进制表示：
● 最末位一个1会变成0● 最末位一个1之后的0会全部变成1
● 其他位相同
栗子：
x = 1011 0000
x-1= 1010 1111
x & (x-1) = 1010 0000
于是，n&(n-1)这个操作，可以起到“消除最后一个1”的功效。
思路：逐步通过n&(n-1)，来消除n末尾的1，消除了多少次，就有多少个1。
伪代码：
while(n){
result++;
n&=(n-1);
}
分析：这个方法，n的二进制表示有多少个1，就会计算多少次。总的来说，n的长度是32bit，如果n的值选取完全随机，平均期望由16个1构成，平均下来16次，节省一半的计算量。
画外音：校招时，我问过这样的面试题，“如何快速判断一个正整数是不是2的x次幂”，巧妙解法是
return !(n&(n-1));
即，如果n是2的x次幂，二进制表示只有一个1。
三、查表法
空间换时间，是算法优化中最常见的手段，如果有相对充裕的内存，可以有更快的算法。
思路：一个uint32的正整数n，一旦n的值确定，n的二进制表示中包含多少个1也就确定了，理论上无需重新计算：
1的二进制表示中包含1个1
2的二进制表示中包含1个1
3的二进制表示中包含2个1
…
58585858的二进制表示中包含15个1
...
提前计算好结果数组：
result[1]=1;
result[2]=1;
result[3]=2;
…
result[58585858]=15;
…
伪代码：
return result[n];
查表法的好处是，时间复杂度为O(1)，潜在的问题是，需要很大的内存。
内存分析：
假如被分析的整数是uint32，打表数组需要记录2^32个正整数的结果。
n的二进制表示最多包含32个1，存储结果的计数，使用5个bit即可。
故，共需要内存2^32 * 5bit = 2.5GB。
画外音：5个bit，能表示00000-11111这32个数。帮忙看下，算错了没有，上一篇文章bit和Byte算错了8倍。
四、二次查表法
查表法，非常快，只查询一次，但消耗内存太大，在工程中几乎不被使用。
算法设计，本身是一个时间复杂度与空间复杂度的折衷，增加计算次数，往往能够减少存储空间。
思路：
（1）把uint32的正整数n，分解为低16位正整数n1，和高16正整数n2；
（2）n1查一次表，其二进制表示包含a个1；
（3）n2查一次表，其二进制表示包含b个1；
（4）则，n的二进制表示包含a+b个1；
伪代码：
uint16 n1 = n & 0xFFFF;
uint16 n2 = (n>>16) & 0xFFFF;
return result[n1]+result[n2];
问题来了：增加了一倍的计算量（1次查表变2次查表），内存空间是不是对应减少一半呢？
内存分析：
被分析的整数变成uint16，打表数组需要记录2^16个正整数的结果。
n1和n2的二进制表示最多包含16个1，存储结果的计数，使用4个bit即可。
故，共需要内存2^16 * 4bit = 32KB。
画外音：帮忙看下，算错了没有。
好神奇！！！
计算量多了1次（1倍），内存占用量却由2.5G降到了32K（1万多倍），是不是很有意思？
五、总结
数1，不难；但其思路有优化过程，并不简单：
（1）位移法，32次计算；
（2）n&(n-1)，能消除一个1，平均16次计算；
（3）查表法，1次查表，2.5G内存；
（4）二次查表法，2次查表，32K内存；
知其然，知其所以然。
思路比结论重要。
希望大家对“数1”有新的认识，谢转。
原文发布时间为：2018-09-26
本文作者：58沈剑
