上一篇:Bits Twiddling Hacks 解析 (二)
「2 為底的整數 log」跟 「count tailing zeroes」 某些程度來說是一樣的問題。因為:
v & (-v)
取出最低位的 1原文:Find the log base 2 of an integer with the MSB N set in O(N) operations (the obvious way)
問題:給一個無號整數 v
,找出 。最直覺的方法就是迴圈寫:
原文:Find the log base 2 of an N-bit integer in O(lg(N)) operations with multiply and lookup
這個思考方式是這樣:如果可以構造出一個 1-1 onto 的函數 ,使得:
那就可以建一個大小是 32 的表,先用 把 2 的冪次對應到整數中,再去查對應的數值就可以了:
剩下的問題就是這個 要怎麼造出來。這邊有一個神奇的造法是這樣:
或是直接:
0x077CB531U
有一個特別的性質:把它做 (0x077CB531U << i)
,其中 ,並且取出最高的 5 個位元時,剛好結果會 0 ~ 31 恰出現一次。這種性質數字叫做 De Bruijn Series。既然 n
已經是 2 的冪次,所以 (n * 0x077CB531U)
其實就是在做右左移。
那就把他變成 2 的冪次:
加入那個 9 ~ 13 行的那堆 OR 之後,就會把這個東西變成:
所以再 +1 之後,就會變成:
然後問題就回到之前的方法。只是表格要重新調整一下(因為結果會比原先多左移一位)。
原文:Find the log base 2 of an N-bit integer in O(lg(N)) operations with multiply and lookup
既然剛剛是「先把東西變成一排 1 再 +1」,那就忍不住想要問:有沒有辦法做直接把一排 1 對應到 0 ~ 31 的整數。也就是構造下面這樣的 1-1 onto mapping:
然後就可以不用做 v + 1
,直接查 table[g(n)]
就好?答案是可以,換一個 magic number 就可以了:
這個數字為什麼可以做到這件事?我想到的解釋大概如下:對於任意有:
形式的數字 v
,直接把他跟 B := 0x07C4ACDDU
相乘,實際上是在做:
這時候要做一件不能隨便做的事:問能不能把上面那個東西展開成這樣:
然後因為 B >> 27
是 0
,所以上面的東西似乎有機會變成:
箭頭右邊會回到「剛好是二的冪次」的做法。那問題就是:這樣可不可以?一般來說這種做法並不保證成立。但只要枚舉所有可能的 v
,然後說它都成立就好。所以就暴力枚舉看看:
發現兩者剛好相差一個位置:
所以會發現:其實可以。只是在建表的時候要重新調整一下位置。
概念是「把整數轉浮點數,然後取出 exponent」。不過這個前提是要知道是使用 IEEE 754。另外還有 byte ordering 要考慮,所以實際上會複雜一點:
問題:給定一個整數 v
,問這個數從最低位開始,連續出現了多少 0
?
最直覺的做法就是一直位移,直到出現非 0 位元為止:
這個做法用二元搜尋去找第一個 1 的位置:先看有沒有在最低 16 位元?
以此遞迴下去。
原文:Count the consecutive zero bits (trailing) on the right in parallel
可以想成上面的改良版,只是適用扣的:
或是用另外一個角度思考:結果一定是 0 ~ 32 其中一個數。但是是不是 32 可以由 v
是否為 0 判斷。如果不是 0
,那麼 c
不可能是 32,所以就扣 1。
排除了 n = 32
的狀況後,接著看結果是 0 ~ 31 的狀況。假定結果是 n
,那麼因為 ,所以 n
會是個 5 位元的數字,也就是有以下的形式:
其中 是 0
或 1
。第 5 ~ 9 就是在問 是 0 還是 1
原文:Count the consecutive zero bits (trailing) on the right by casting to a float
關鍵是 IEEE-754 中的 exponent
可以用 0x7f800000
去找出來。把無號數 v
最低位的位元取出來(v & -v
) 並轉型成浮點數之後,把對應的 exponent
找出來並且反推回數值:
問題:讓兩個數字的位元交錯。比如 x
的二進位形式是 ABCDEFGH
,而 y
的二進位形式是 abcdefgh
,那麼求出的結果 r
的二進位形式為 AaBbCcDdEeFfGgHh
。
大致上的思路是這樣:
一樣是窮舉一個 byte 中所有可能的數值。假定某個 byte b
的二進位形式是 b = ABCDFEGH
,那麼 table[b]
將會查到一個二進位形式是 0A0B0C0D0E0F0G0H
的數值 (也就是在所有位元間加入 0
把他們隔開的結果)。
比如說:221
的二進位是 11011101
,那麼 table[221]
就會查到「每個位元左邊都插入 1 個 0」的結果,也就是 01 01 00 01 01 01 00 01
。窮舉出這個表:
在這樣的狀況下,對於一個 byte 來說,只要做:
就可以得出位元交叉混合的結果了。有了一個 byte 的做法後,可以把它推廣到交錯地合併 2 個 short
,組合出一個 int
的做法:
這個做法仿照「逆轉所有位元」的方法,用下面這組 mask:
主要的思路是先把位元打散,以 8 位元來說,假定位元表示是 ABCDEFGH
,而「打散」的結果就是 0A0B0C0D0F0G0H
,而「打散」的做法是使用分治法。以 8 位元為例,就是不斷地交換不同間隔的位元:
把同樣的想法推廣到「交叉合併 2 個 16 位元整數」的話,就會得到文章中的 code:
跟 8 位元的想法幾乎一樣,只是把位元寬度變長,而跟著調整那組 mask 跟位移的長度。
跟前面位元反轉用的分治方式是一樣的。這邊舉合併兩個 byte 為例。假設 b1
的二進位表示法是 ABCDEFGH
,而 b2
的二進位表示法是 abcdefgh
,那每次