Assembly 計算位數(shù)的3種方法

前面介紹了一個簡單的技術(shù)來計算一個雙字中“on”的位數(shù)有多少。這一節(jié)來看看其它不是很直接來做這件事的方法，就當(dāng)作使用在這一章中討論的位操作的練習(xí)。

方法一

第6行表示data中的一個比特位被關(guān)閉了。這個是如何起作用的？考慮data二進(jìn)制表示法最普遍的格式和在這種表示法中最右邊的1。根據(jù)上面的定義，在這個1后面的所有位都為0。現(xiàn)在，data -1的二進(jìn)制表示是什么樣的？最右邊的1的所有左邊的位與data是一樣的，但是在最右邊的1這一點(diǎn)的位將會是data原始位的反碼。例如：

data        = xxxxx10000
data - 1   = xxxxx01111

x表示對于在這個位上這兩個數(shù)的值是相等的。當(dāng)data和data - 1進(jìn)行AND運(yùn)算后，在data中的最右邊的1這一位的結(jié)果就會為0，而其它比特位沒有被改變。

方法二

查找表同樣可以用來計算出任意雙字的位數(shù)。這個直接方法首先要算出每個雙字的位數(shù)，還要把位數(shù)儲存到一個數(shù)組中。但是，有兩個與這個方法相關(guān)的問題。雙字的值大約有40億。這就意味著數(shù)組將會非常大而且會浪費(fèi)很多時間在初始化這個數(shù)組上。(事實(shí)上，除非你確實(shí)打算使用一個超過40億的數(shù)組，否則花在初始化這個數(shù)組的時間將遠(yuǎn)遠(yuǎn)大于用第一種方法計算位數(shù)的時間。

一個更現(xiàn)實(shí)的方法是提前算出所有可能的字節(jié)的位數(shù)，并把它們儲存到一個數(shù)組中。然后，雙字就可以分成四個字節(jié)來求。這四個字節(jié)的位數(shù)通過查找數(shù)組得到，然后將它們相加就得到原始雙字的位數(shù)。圖3.7展示了如何用代碼實(shí)現(xiàn)這個方法。

initialize_count bits函數(shù)必須在第一次調(diào)用count bits函數(shù)之前被調(diào)用。這個函數(shù)初始化了byte_bit_count全局?jǐn)?shù)組。count_bits函數(shù)并不是以一個雙字來看對待data變量，而是以把它看成四個字節(jié)的數(shù)組。byte指針作為一個指向這個四個字節(jié)數(shù)組的指針。因此，byte[0]是data中的一個字節(jié)(是最低有效字節(jié)還是最高有效字節(jié)取決于硬件是使用little還是big endian。)。當(dāng)然，你可以像這樣使用一條指令：

(data >> 24) & 0x000000FF

來得到最高有效字節(jié)值，可以用同樣的方法得到其它字節(jié)；但是這些指令會比引用一個數(shù)組要慢。
最后一點(diǎn)，使用for循環(huán)來計算在22和23行的總數(shù)是簡單的。但是，for循環(huán)就會包含初始化一個循環(huán)變量，在每一次重復(fù)后比較這個變量和增加這個變量的時間開支。通過清楚的四個值來計算總數(shù)會快一些。事實(shí)上，一個好的編譯器會將for循環(huán)形式轉(zhuǎn)換成清楚的求和。這個簡化和消除循環(huán)重復(fù)的處理是一個稱為循環(huán)展開的編譯器優(yōu)化技術(shù)。

方法三

這個做了些什么？十六進(jìn)制常量0x55的二進(jìn)制表示為01010101。在這個加法的第一個操作數(shù)中，data與這個常量進(jìn)行了AND運(yùn)算，奇數(shù)的位就被拿出來了。第二操作數(shù)((data >> 1) & 0x55)，首先移動所有的偶數(shù)位到奇
數(shù)位上，然后使用相同的掩碼得到這些相同的位?，F(xiàn)在，第一個操作數(shù)含有data的奇數(shù)位而第二個操作數(shù)含有偶數(shù)位。把這兩個操作數(shù)相加就相當(dāng)于把data的奇數(shù)位和偶數(shù)位相加。例如，如果data等于，那么：

使用上面的例子(data等于):