2000/04/23 [日]
フラグ変数の特定のビットが 1 になっているかどうかを検出するのは容易ですが、その変数で 1 になっているビットを探していくのは大変です。たいていループを使って探していく記述にすることが多いかと思います。しかし、1 になっている最下位ビットのより効率的な検出方法があります(ただし以下で示すのは 2 の補数用)。それは、フラグ変数を x とすると x & -x を計算するという方法です。具体的には次のようになります。
このように、1 になっている最下位ビットが正しく検出されていることがわかります。また x & -x の計算結果 y を利用して x ^= y という計算を行うと次々 1 が立っているビットを探していくことができます。
| x | -x | x & -x | 最下位 ビット |
|---|---|---|---|
| 000 | 000 | 000 | × |
| 001 | 111 | 001 | b1 |
| 010 | 110 | 010 | b2 |
| 011 | 101 | 001 | b1 |
| 100 | 100 | 100 | b4 |
| 101 | 011 | 001 | b1 |
| 110 | 010 | 010 | b2 |
| 111 | 001 | 001 | b1 |
このように、1 になっている最下位ビットが正しく検出されていることがわかります。また x & -x の計算結果 y を利用して x ^= y という計算を行うと次々 1 が立っているビットを探していくことができます。
by seclan