整数内の最下位セットビットの位置を効率的に見つけるにはどうすればよいですか?

最下位セットビットの位置の決定

プログラミングにおいて、セットされる最下位ビット (LSB) の位置を決定することinteger は便利な演算です。単純な実装では、整数を 1 で繰り返しマスクし、結果が 0 以外になるまで右シフトする必要がありますが、この方法は大きな整数の場合は遅くなる可能性があります。

ビットいじりの最適化

ちょっとしたハックは効率的な代替手段を提供します。このようなハッキングの 1 つは、「乗算と検索」メソッドとして知られており、de Bruijn シーケンスのプロパティを利用して、単一ステップで計算を実行します。

コードの実装

unsigned int v;  // find the number of trailing zeros in 32-bit v
int r;           // result goes here
static const int MultiplyDeBruijnBitPosition[32] = 
{
  0, 1, 28, 2, 29, 14, 24, 3, 30, 22, 20, 15, 25, 17, 4, 8, 
  31, 27, 13, 23, 21, 19, 16, 7, 26, 12, 18, 6, 11, 5, 10, 9
};
r = MultiplyDeBruijnBitPosition[((uint32_t)((v & -v) * 0x077CB531U)) >> 27];

説明

このコードは次のように動作します。整数 v にマジック定数を乗算し、その結果に対してビット シフトを実行します。 MultiplyDeBruijnBitPosition 配列は、乗算の結果を LSB の目的の位置にマップします。

利点と参考

このメソッドは、特に次の場合、単純な実装よりも大幅に高速です。大きな整数。この手法の詳細な説明と詳細については、

• 「Using de Bruijn Sequences to Index a 1 in a Computer Word」
• 「ボード表現」>「ビットボード」>「

」を参照してください。ビットスキャン「」

以上が整数内の最下位セットビットの位置を効率的に見つけるにはどうすればよいですか?の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。