一次搞透，面试中的数1问题的五种方法！

面试中，一次搞透除了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)最末位一个1会变成0;

(2)最末位一个1之后的0会全部变成1;

(3)其他位相同;

栗子：

           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次，网站模板节省一半的计算量。

三、查表法。

空间换时间，是算法优化中最常见的手段，如果有相对充裕的内存，可以有更快的算法。

思路：一个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个数。

四、二次查表法。

查表法，非常快，只查询一次，但消耗内存太大，在工程中几乎不被使用。

算法设计，本身是一个时间复杂度与空间复杂度的折衷，增加计算次数，往往能够减少存储空间。

思路：

(1)把uint32的正整数n，分解为低16位正整数n1，和高16正整数n2;

(2)n1查一次表，其二进制表示包含a个1;

(3)n2查一次表，其二进制表示包含b个1;

(4)则，n的二进制表示包含a+b个1;

伪代码：

uint16 nn1 = 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次，内存占用量却由2.5G降到了32K(1万多倍)，是不是很有意思?

五、总结

数1，不难;但其思路有优化过程，并不简单：

(1)位移法，32次计算;

(2)n&(n-1)，能消除一个1，平均16次计算;

(3)查表法，1次查表，2.5G内存;

(4)二次查表法，2次查表，32K内存;

知其然，知其所以然。

思路比结论重要。

【本文为专栏作者“58沈剑”原创稿件，转载请联系原作者】

戳这里，看该作者更多好文