一次搞透，面試中的數(shù)1問題的五種方法！

面試中，除了TopK，是否被問過：求一個正整數(shù)的二進(jìn)制表示包含多少個1？

畫外音：姊妹篇《一次搞透，面試中的TopK問題！》。

例如：

uint32_t i=58585858;

i的二進(jìn)制表示是：

0000 0011 0111 1101 1111 0011 0000 0010

于是，i的二進(jìn)制表示包含15個1。

?

到底有幾種方法，這些思路里蘊(yùn)含的優(yōu)化思路究竟是怎么樣的，今天和大家聊一聊。

?

一、位移法。

思路：既然輸入n是uint32，每次取n的最低位，判斷是不是1，位移32次，循環(huán)判斷即可。

?

偽代碼：

do{

? ? if ((n&1)==1){

???????result++;

??? }

??? n>>= 1;

? ? i++;

} while(i<32);

?

分析：不管n的二進(jìn)制表示里包含多少個1，都需要循環(huán)計算32次，比較耗時。有沒有可能，每次消除掉一個1，這樣來降低計算次數(shù)呢？

?

二、求與法。

觀察一下n與n-1這兩個數(shù)的二進(jìn)制表示：

（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的二進(jìn)制表示有多少個1，就會計算多少次?？偟膩碚f，n的長度是32bit，如果n的值選取完全隨機(jī)，平均期望由16個1構(gòu)成，平均下來16次，節(jié)省一半的計算量。

?

三、查表法。

空間換時間，是算法優(yōu)化中最常見的手段，如果有相對充裕的內(nèi)存，可以有更快的算法。

?

思路：一個uint32的正整數(shù)n，一旦n的值確定，n的二進(jìn)制表示中包含多少個1也就確定了，理論上無需重新計算：

1的二進(jìn)制表示中包含1個1

2的二進(jìn)制表示中包含1個1

3的二進(jìn)制表示中包含2個1

…

58585858的二進(jìn)制表示中包含15個1

...

?

提前計算好結(jié)果數(shù)組：

result[1]=1;

result[2]=1;

result[3]=2;

…

result[58585858]=15;

…

?

偽代碼：

return result[n];

?

查表法的好處是，時間復(fù)雜度為O(1)，潛在的問題是，需要很大的內(nèi)存。

?

內(nèi)存分析：

假如被分析的整數(shù)是uint32，打表數(shù)組需要記錄2^32個正整數(shù)的結(jié)果。

n的二進(jìn)制表示最多包含32個1，存儲結(jié)果的計數(shù)，使用5個bit即可。

故，共需要內(nèi)存2^32 * 5bit = 2.5GB。

畫外音：5個bit，能表示00000-11111這32個數(shù)。

?

四、二次查表法。

查表法，非?？欤徊樵円淮?，但消耗內(nèi)存太大，在工程中幾乎不被使用。

?

算法設(shè)計，本身是一個時間復(fù)雜度與空間復(fù)雜度的折衷，增加計算次數(shù)，往往能夠減少存儲空間。

?

思路：

（1）把uint32的正整數(shù)n，分解為低16位正整數(shù)n1，和高16正整數(shù)n2；

（2）n1查一次表，其二進(jìn)制表示包含a個1；

（3）n2查一次表，其二進(jìn)制表示包含b個1；

（4）則，n的二進(jìn)制表示包含a+b個1；

?

偽代碼：

uint16 n1 = n & 0xFFFF;

uint16 n2 = (n>>16) & 0xFFFF;

return ?result[n1]+result[n2];

?

問題來了：增加了一倍的計算量（1次查表變2次查表），內(nèi)存空間是不是對應(yīng)減少一半呢？

?

內(nèi)存分析：

被分析的整數(shù)變成uint16，打表數(shù)組需要記錄2^16個正整數(shù)的結(jié)果。

n1和n2的二進(jìn)制表示最多包含16個1，存儲結(jié)果的計數(shù)，使用4個bit即可。

故，共需要內(nèi)存2^16 * 4bit = 32KB。

?

好神奇?。?！

計算量多了1次，內(nèi)存占用量卻由2.5G降到了32K（1萬多倍），是不是很有意思？

?

五、總結(jié)

數(shù)1，不難；但其思路有優(yōu)化過程，并不簡單：

（1）位移法，32次計算；

（2）n&(n-1)，能消除一個1，平均16次計算；

（3）查表法，1次查表，2.5G內(nèi)存；

（4）二次查表法，2次查表，32K內(nèi)存；

?

知其然，知其所以然。

思路比結(jié)論重要。

架構(gòu)師之路-分享可落地的架構(gòu)文章

推薦閱讀：

《世界上最美的排序算法！》

《世界上最慢的排序算法！》

《世界上最開腦洞的排序算法！》