閱讀(4.7k) 書(shū)簽贊(0) 我要糾錯(cuò)

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

2018-10-28 11:45 更新

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

方法一

第一個(gè)方法很簡(jiǎn)單，但不是很明顯。圖3.6展示了代碼。

這個(gè)方法為什么會(huì)起作用？在循環(huán)中的每一次重復(fù)，data中就會(huì)有一個(gè)比特位被關(guān)閉了。當(dāng)所有的位都關(guān)閉了(也就是說(shuō)，當(dāng)data 等于0了)，循環(huán)就結(jié)束了。使data等于0需要重復(fù)的次數(shù)就等于原始值data中比特位為1的位數(shù)。

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

data = xxxxx10000
data - 1 = xxxxx01111

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

方法二

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

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

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

(data >> 24) & 0x000000FF

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

方法三

現(xiàn)在還有一個(gè)更聰明的方法來(lái)計(jì)算在數(shù)據(jù)里的位數(shù)。這個(gè)方法逐位地相加數(shù)據(jù)的0位和1位。得到的總數(shù)就等于在這個(gè)數(shù)據(jù)中1的位數(shù)。例如，考慮計(jì)算儲(chǔ)存在data變量中的一個(gè)字節(jié)中為1的位數(shù)。第一步是執(zhí)行下面這個(gè)操作：

data = (data & 0x55) + ((data >> 1) & 0x55);

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

，那么：

顯示在右邊的加法展示了實(shí)際的位相加。這個(gè)字節(jié)的位被分成了四個(gè)2位的字段來(lái)展示實(shí)際上執(zhí)行了四個(gè)獨(dú)立的加法。因?yàn)樗羞@些字段的最大總數(shù)為2，總數(shù)超過(guò)它自身的字段且影響到其它字段的總數(shù)是不可能的。

當(dāng)然，總的位數(shù)還沒(méi)被計(jì)算出來(lái)。但是，可以使用跟上面一樣的技術(shù)，經(jīng)過(guò)同樣的步驟來(lái)計(jì)算總數(shù)。下一步應(yīng)該是：

現(xiàn)在有兩個(gè)4位的字段被單獨(dú)地相加。

下一步是通過(guò)把這兩位的總數(shù)相加來(lái)得到最終的結(jié)果：

data = (data & 0x0F) + ((data >> 4) & 0x0F);

使用上面的例子(data等于

):

現(xiàn)在data等于5，這正好是正確的結(jié)果。圖3.8實(shí)現(xiàn)了用這個(gè)方法來(lái)計(jì)算一個(gè)雙字的位數(shù)。它使用了一個(gè)for循環(huán)來(lái)計(jì)算總數(shù)。把循環(huán)展開(kāi)可能會(huì)更快一點(diǎn)，但是使用循環(huán)能清晰地看到這個(gè)方法產(chǎn)生的不同大小的數(shù)據(jù)。