計算機科學論壇最近舉辦了一個閱讀樣章，提交書評的活動，具體內容請見http://www.ieee.org.cn/dispbbs.asp?boardID=42&ID=61162。
這里我想針對樣章上的一個問題談談自己的理解。
問題很簡單，求二進制中1的個數。對于一個字節（8bit）的變量，求其二進制表示中"1"的個數，要求算法的執行效率盡可能的高。
先來看看樣章上給出的幾個算法：
解法一，每次除二，看是否為奇數，是的話就累計加一，最后這個結果就是二進制表示中1的個數。
解法二，同樣用到一個循環，只是里面的操作用位移操作簡化了。
?? 1:? int Count(int v)??
?? 2:? {??
?? 3:????? int num = 0;
?? 4:????? while (v) {??
?? 5:????????? num += v & 0x01;??
?? 6:????????? v >>= 1;??
?? 7:????? }??
?? 8:????? return num;??
?? 9:? }
解法三，用到一個巧妙的與操作，v & (v -1 )每次能消去二進制表示中最后一位1，利用這個技巧可以減少一定的循環次數。
解法四，查表法，因為只有數據8bit，直接建一張表，包含各個數中1的個數，然后查表就行。復雜度O(1)。
?? 1:? int countTable[256] = { 0, 1, 1, 2, 1, ..., 7, 7, 8 };??
?? 2:?????
?? 3:? int Count(int v) {??
?? 4:????? return countTable[v];??
?? 5:? }
??
好了，這就是樣章上給出的四種方案，下面談談我的看法。
首先是對算法的衡量上，復雜度真的是唯一的標準嗎？尤其對于這種數據規模給定，而且很小的情況下，復雜度其實是個比較次要的因素。
查表法的復雜度為O(1)，我用解法一，循環八次固定，復雜度也是O(1)。至于數據規模變大，變成32位整型，那查表法自然也不合適了。
其次，我覺得既然是這樣一個很小的操作，衡量的尺度也必然要小，CPU時鐘周期可以作為一個參考。
解法一里有若干次整數加法，若干次整數除法（一般的編譯器都能把它優化成位移），還有幾個循環分支判斷，幾個奇偶性判斷（這個比較耗時間，根據CSAPP上的數據，一般一個branch penalty得耗掉14個左右的cycle），加起來大概幾十個cycle吧。
再看解法四，查表法看似一次地址計算就能解決，但實際上這里用到一個訪存操作，而且第一次訪存的時候很有可能那個數組不在cache里，這樣一個cache miss導致的后果可能就是耗去幾十甚至上百個cycle（因為要訪問內存）。所以對于這種“小操作”，這個算法的性能其實是很差的。
這里我再推薦幾個解決這個問題的算法，以32位無符號整型為例。
?? 1:? int Count(unsigned x) {??
?? 2:???? x = x - ((x >> 1) & 0x55555555);???
?? 3:???? x = (x & 0x33333333) + ((x >> 2) & 0x33333333);???
?? 4:???? x = (x + (x >> 4)) & 0x0F0F0F0F;???
?? 5:???? x = x + (x >> 8);???
?? 6:???? x = x + (x >> 16);???
?? 7:???? return x & 0x0000003F;???
?? 8:? }
??
這里用的是二分法，兩兩一組相加，之后四個四個一組相加，接著八個八個，最后就得到各位之和了。
還有一個更巧妙的HAKMEM算法
?? 1:? int Count(unsigned x) {
?? 2:???? unsigned n;???
?? 3:?????
?? 4:???? n = (x >> 1) & 033333333333;???
?? 5:???? x = x - n;??
?? 6:???? n = (n >> 1) & 033333333333;??
?? 7:???? x = x - n;???
?? 8:???? x = (x + (x >> 3)) & 030707070707;??
?? 9:???? x = modu(x, 63);?
?? 10:???? return x;??
?? 11:? }
??
首先是將二進制各位三個一組，求出每組中1的個數，然后相鄰兩組歸并，得到六個一組的1的個數，最后很巧妙的用除63取余得到了結果。
因為2^6 = 64，也就是說 x_0 + x_1 * 64 + x_2 * 64 * 64 = x_0 + x_1 + x_2 (mod 63)，這里的等號表示同余。
這個程序只需要十條左右指令，而且不訪存，速度很快。
由此可見，衡量一個算法實際效果不單要看復雜度，還要結合其他情況具體分析。
關于后面的兩道擴展問題，問題一是問32位整型如何處理，這個上面已經講了。
問題二是給定兩個整數A和B，問A和B有多少位是不同的。
這個問題其實就是數1問題多了一個步驟，只要先算出A和B的異或結果，然后求這個值中1的個數就行了。
總體看來這本書還是很不錯的，比較喜歡里面針對一個問題提出不同算法并不斷改進的風格。這里提出一點個人的理解，望大家指正 ;-)
(by ZelluX?? http://m.tkk7.com/zellux)