一道筆試題--求二進制數1的個數

要進一家新公司難免要進行筆試，雖然筆試通過的人很多都有背題之嫌，但是統計意義上最起碼可以看出一個程式員的認真程度，畢竟很多公司的考題也不是自己創的，也是在網上偷的，允許公司偷題就必須允許應聘者偷答案。短時間背下來答案并不難，難的是真正了解這些算法背後的思想，很多人在筆試期間可能一個也寫不出來，但是隻要寫下來一些東西，很可能就被奇迹般錄取了，應聘可不是聯考，标準統一，有時一道筆試題你即使寫不出來，但是讓主審看出來你在使用一個小技巧，比如遞歸，那麼他别的什麼也不看就可能收你了。以下是我去年去一家公司應聘時的筆試題，當時我寫下了以下的方法，語言是java：

int OneCount0(int i)

{

//将i轉化為二進制字元串

String str = i + "";

//然後用StringBuffer類進行按順序掃面，掃面字元'1'

}

然後又附上了以下三種方法，說實話OneCount0和OneCount1以及OneCount2是都是我自己想出來的，OneCount3是别人的，其實這不所謂自己的和别人的，隻要你有計算機位運算的基礎，OneCount1到OneCount3都是可以得到的，OneCount0是最笨的，我也不知道為何把這個笨方法作為了最終答案。答完之後考官問我為何如此寫，我說沒什麼，就是要對待java公平一些，考官就是做java的，但是考官卻認為我是故意戲弄他，當我将所有的題都答出并且多數答對之後，他又問我為何這麼寫，我就聊到了cpu的L1,L2的cache，聊到了堆棧，取指，指令流水線...我突然覺得我上當了，天真的我教會了考官那麼多東西，天啊，我把那家公司拒了！這個考官簡直什麼也不懂，估計做java的大多都這樣吧(但是真正的java高手同時也是c高手，不懂底層知識的占少數，隻是國内真正的java高手太少了)，由于缺錢我應聘了一個比較簡單的java職位，沒有想到受到如此打擊，欲哭無淚啊！我本将心向明月，奈何明月照溝渠！

unsigned int OneCount1( unsigned int i )

unsigned int count = 0;

unsigned int onetwo;

do

onetwo = i%2;

i = i/2; //i = i>>1;

count += onetwo?1:0;

}while ( i != 0 );

return count;

這個算法是顯而易見的，其實就是将十進制轉換為二進制的算法，轉換過程中肯定對一個數字是1還是0是再清晰不過的，是以順便可以完成統計1的個數的需求，但是效率呢？很差，為何差呢？很多人都知道這個算法的效率很差，原因是用到了循環，用到了除法等等，其實不必這麼定量分析，想想它完成的功能吧，本質來講，統計1的數目就是一個捎帶的過程，從該算法的副作用上講，它的效率并不算差，如果有硬體幫忙，它實際上是将十進制的數字轉換成了二進制的表示方法，而不僅僅是統計了1的數目。

unsigned OneCount2(unsigned int i)

int j = 0;

while(x)

i = i&(i-1);

j ++;

return j;

該算法的效率比OneCount1高了不少，因為它去除了不必要的轉換表示法的操作，僅僅就是統計了1的數目，一個&操作将努力使資料的高位清除，因為該算法是收斂的，努力使自己沒有事情要做，是以onetwo = i%2之類的就沒有了，onetwo?1:0;之類的判斷指派也沒有了，直接一個位運算除了統計了1的數目之外再沒有别的用處，每次x和x-1的與運算可以将為0的位的數量增加1，比如數字421的二進制為110100101，420的二進制為110100100，最低位的1被抹去了，二者按位相與之後，最低的兩位都成了0，然後結果減1的二進制是110100011，最低位開始第三位為1，以此類推，總之隻要減1，那麼從低位到高位一直到為1的位，此位将變成0，而更低的位将全部變成1，二者按位與之後，這個遞減之前的1被抹去，一直到結束。這個算法沒有額外的作用，就數1的數量，效率較高。

unsigned long OneCount3(unsigned int x)

x = (x & 0x55555555UL) + ((x >> 1) & 0x55555555UL); //1

x = (x & 0x33333333UL) + ((x >> 2) & 0x33333333UL); //2

x = (x & 0x0f0f0f0fUL) + ((x >> 4) & 0x0f0f0f0fUL); //3

x = (x & 0x00ff00ffUL) + ((x >> 8) & 0x00ff00ffUL); //4

x = (x & 0x0000ffffUL) + ((x >> 16) & 0x0000ffffUL); //5

return x;

雖然OneCount2的效率較高，但是還是用到了判斷，動态位運算，減法等等，即目前如何進行計算依賴于前一次計算的結果，這樣在衆多判斷和動态運算機制之下，不利于利用cpu的硬體cache，如果能運用靜态的表，或者說為了節省存儲空間部分的使用靜态表，然後剩下的部分用動态計算的方式，這就是第三種算法OneCount3.這個算法初看起來不是很好了解，但是比劃幾下似乎又不是很複雜，這個算法巧妙的地方在于一個個按位與最後将1的個數加到了一起，并且最終這個總合被移動到了最右邊，本質上用到了遞歸的方式，隻是沒有用低效的基于棧的函數調用實作罷了。起初這個和是很多個，最終才被加到了一起，在相加的同時向右移動，遞歸結束的條件就是需要移位的寬度和x的寬度一緻，第1行算出了16個和，分别記到了第0，2，4，...30位，必要的話進位到第1，3，5，...31位，比如第0位和第1位都是1，那麼這兩位1的個數就是2，結果就是10，可以看到占用了兩位，其實仔細看一下僅這一步就将1的數量統計了出來，接下來就是将這16個加和加在一起就可以了，第2行的含義和第1行一樣，就是将第1行加和的兩位的結果再次加和，比如第0和第1位的加和為10，第2和第3位的加和為10，那麼這四位的加和就是10+10=100，必要時進位到更高的位，但是進位不會超過兩位，依次類推。

以上三種方式我在自己機器上進行了測試，用RDTSC指令測速，發現第三個算法最快，第一個最慢，但是如果我将三個算法放到一個程式中緊接着測試并且将OneCount1排到OneCount2和OneCount3之後運作卻發現OneCount1是最快的，其實這是cpu緩存的作用，在OneCount2和OneCount3執行時已經在cache緩存了很多資料，等到OneCount1執行時就不用在訪存了。

 本文轉自 dog250 51CTO部落格，原文連結:http://blog.51cto.com/dog250/1274094