在寫程式的時候，一般來說，常見的程式語言所提供的運算（像是加法、減法、位元運算等等），都能應付絕大多數的需求。不過，偶而有時會出現一些相當麻煩的問題。例如，假設一個 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。