seclan のほえほえルーム

| |

1 になっている最下位ビットの高速検出方法

・
2000/04/23 []

 フラグ変数の特定のビットが 1 になっているかどうかを検出するのは容易ですが、その変数で 1 になっているビットを探していくのは大変です。たいていループを使って探していく記述にすることが多いかと思います。しかし、1 になっている最下位ビットのより効率的な検出方法があります(ただし以下で示すのは 2 の補数用)。それは、フラグ変数を x とすると x & -x を計算するという方法です。具体的には次のようになります。

x-xx & -x最下位
ビット
000000000×
001111001b1
010110010b2
011101001b1
100100100b4
101011001b1
110010010b2
111001001b1

 このように、1 になっている最下位ビットが正しく検出されていることがわかります。また x & -x の計算結果 y を利用して x ^= y という計算を行うと次々 1 が立っているビットを探していくことができます。


by seclan

関連


| |

 

配信

6.05 msec