Bit Scan Trick
 

在寫程式的時候,一般來說,常見的程式語言所提供的運算(像是加法、減法、位元運算等等),都能應付絕大多數的需求。不過,偶而有時會出現一些相當麻煩的問題。例如,假設一個 32 bits 數字中,只有一個位元是 1,而我們想知道那是第幾個位元(從 least significant bit 開始算起),那要怎麼做呢?(例如,0x00080000 是第 19 個位元是 1)

很明顯的,這可以用一個簡單的迴圈來解決,如下:

int i = 0;
int m = 1;
while(number != m) {
    i++;
    m <<= 1;
}

當然,這不是最好的方法。比較明顯的解決方法是建一個表。例如,以 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;
i += (number & 0xAAAAAAAA) ? 1 : 0;
i += (number & 0xCCCCCCCC) ? 2 : 0;
i += (number & 0xF0F0F0F0) ? 4 : 0;
i += (number & 0xFF00FF00) ? 8 : 0;
i += (number & 0xFFFF0000) ? 16 : 0;

這樣一來,不需要查表,只要五行程式碼就可以計算出結果了。很有趣吧!

當然,這招只對只有一個位元是 1 的時候有作用,所以它並不能取代真正的 bit scan。