計算機(jī)科學(xué)論壇最近舉辦了一個閱讀樣章，提交書評的活動，具體內(nèi)容請見http://www.ieee.org.cn/dispbbs.asp?boardID=42&ID=61162。
這里我想針對樣章上的一個問題談?wù)勛约旱睦斫狻?/p>
問題很簡單，求二進(jìn)制中1的個數(shù)。對于一個字節(jié)（8bit）的變量，求其二進(jìn)制表示中"1"的個數(shù)，要求算法的執(zhí)行效率盡可能的高。
先來看看樣章上給出的幾個算法：
解法一，每次除二，看是否為奇數(shù)，是的話就累計加一，最后這個結(jié)果就是二進(jìn)制表示中1的個數(shù)。
解法二，同樣用到一個循環(huán)，只是里面的操作用位移操作簡化了。
?? 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 )每次能消去二進(jìn)制表示中最后一位1，利用這個技巧可以減少一定的循環(huán)次數(shù)。
解法四，查表法，因為只有數(shù)據(jù)8bit，直接建一張表，包含各個數(shù)中1的個數(shù)，然后查表就行。復(fù)雜度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:? }
??
好了，這就是樣章上給出的四種方案，下面談?wù)勎业目捶ā?/p>
首先是對算法的衡量上，復(fù)雜度真的是唯一的標(biāo)準(zhǔn)嗎？尤其對于這種數(shù)據(jù)規(guī)模給定，而且很小的情況下，復(fù)雜度其實是個比較次要的因素。
查表法的復(fù)雜度為O(1)，我用解法一，循環(huán)八次固定，復(fù)雜度也是O(1)。至于數(shù)據(jù)規(guī)模變大，變成32位整型，那查表法自然也不合適了。
其次，我覺得既然是這樣一個很小的操作，衡量的尺度也必然要小，CPU時鐘周期可以作為一個參考。
解法一里有若干次整數(shù)加法，若干次整數(shù)除法（一般的編譯器都能把它優(yōu)化成位移），還有幾個循環(huán)分支判斷，幾個奇偶性判斷（這個比較耗時間，根據(jù)CSAPP上的數(shù)據(jù)，一般一個branch penalty得耗掉14個左右的cycle），加起來大概幾十個cycle吧。
再看解法四，查表法看似一次地址計算就能解決，但實際上這里用到一個訪存操作，而且第一次訪存的時候很有可能那個數(shù)組不在cache里，這樣一個cache miss導(dǎo)致的后果可能就是耗去幾十甚至上百個cycle（因為要訪問內(nèi)存）。所以對于這種“小操作”，這個算法的性能其實是很差的。
這里我再推薦幾個解決這個問題的算法，以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:? }
??
首先是將二進(jìn)制各位三個一組，求出每組中1的個數(shù)，然后相鄰兩組歸并，得到六個一組的1的個數(shù)，最后很巧妙的用除63取余得到了結(jié)果。
因為2^6 = 64，也就是說 x_0 + x_1 * 64 + x_2 * 64 * 64 = x_0 + x_1 + x_2 (mod 63)，這里的等號表示同余。
這個程序只需要十條左右指令，而且不訪存，速度很快。
由此可見，衡量一個算法實際效果不單要看復(fù)雜度，還要結(jié)合其他情況具體分析。
關(guān)于后面的兩道擴(kuò)展問題，問題一是問32位整型如何處理，這個上面已經(jīng)講了。
問題二是給定兩個整數(shù)A和B，問A和B有多少位是不同的。
這個問題其實就是數(shù)1問題多了一個步驟，只要先算出A和B的異或結(jié)果，然后求這個值中1的個數(shù)就行了。
總體看來這本書還是很不錯的，比較喜歡里面針對一個問題提出不同算法并不斷改進(jìn)的風(fēng)格。這里提出一點個人的理解，望大家指正 ;-)
(by ZelluX?? http://www.aygfsteel.com/zellux)