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