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

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

[[443193]]

例如：

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，就會計算多少次。總的來說，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 nn1 = 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é)論重要。

【本文為51CTO專欄作者“58沈劍”原創(chuàng)稿件，轉(zhuǎn)載請聯(lián)系原作者】

戳這里，看該作者更多好文