在寫程式的時候,一般來說,常見的程式語言所提供的運算(像是加法、減法、位元運算等等),都能應付絕大多數的需求。不過,偶而有時會出現一些相當麻煩的問題。例如,假設一個 32 bits 數字中,只有一個位元是 1,而我們想知道那是第幾個位元(從 least significant bit 開始算起),那要怎麼做呢?(例如,0x00080000 是第 19 個位元是 1) 很明顯的,這可以用一個簡單的迴圈來解決,如下: int i = 0; 當然,這不是最好的方法。比較明顯的解決方法是建一個表。例如,以 4 bits 為單位建表的話,表的大小是 9(我們假設只有一個 bit 是 1),這樣一個 32 bits 數字需要查八次表。如果建 8 bits 的表,表的大小是 129,只需要查四次。 不過,有的時候建表也不理想,特別是當不希望使用太多記憶體的時候。這時還有別的方法嗎? 當然,最明顯的答案是,有些 CPU 提供 bit scan 的指令,可以找到「第一個 bit」,例如 x86 的 bsr/bsf 指令。不過,如果不希望使用到特定指令集的指令,是否還有別的方法呢? 如果一個 CPU 沒有提供 bit scan 的指令,但是有 population count 的指令(即計算一個數字中位元為 1 的數目),那麼可以用一個很簡單的技巧: n = pop_count(number - 1); 這是因為,如果只有一個 bit 為 1,那麼把數字減 1 時,所有低於該 bit 的位元都會變成 1。因此它的 population count 就是位元的位置。 不過 population count 並不是一般程式語言會內建的運算。如果只使用到一般程式語言的運算(例如 C 語言),是否有更好的方法呢? 當然是有的,不然就不會有這篇文章了。事實上,這個問題可以用二進位來解決。簡單的說,如果位元 1 的位置,是奇數的話,那麼位置的 lsb(least significant bit)就是 1,反之就是 0。要怎麼知道位元 1 的位置是不是奇數呢?很簡單,我們可以把它和 0xAAAAAAAA 進行 bitwise and,如果結果是 0,那它的位置就不是奇數。 同理,對第二個位元也可以進行同樣的動作,即和 0xCCCCCCCC 進行 bitwise and。依此類推,可以得到下面的程式: int i = 0; 這樣一來,不需要查表,只要五行程式碼就可以計算出結果了。很有趣吧! 當然,這招只對只有一個位元是 1 的時候有作用,所以它並不能取代真正的 bit scan。 |
Copyright(c) 2008 Ping-Che Chen