[解決済み] 最下位ビットがセットされる位置

質問

整数で設定されている最下位ビットの位置を決定する効率的な方法を探しています。例えば、0x0FF0 の場合は 4 となります。

些細な実装はこれです。

unsigned GetLowestBitPos(unsigned value)
{
   assert(value != 0); // handled separately

   unsigned pos = 0;
   while (!(value & 1))
   {
      value >>= 1;
      ++pos;
   }
   return pos;
}

どうすればサイクルを絞り込めるか、何かアイデアはありますか？

(注意: この質問はそのようなことを楽しむ人のためのもので、xyzoptimizationが邪悪だと私に言う人のためのものではありません)。

[編集］ 皆さん、アイデアをありがとうございました 他にもいくつか勉強になることがありました。カッコイイ!

どのように解決するのですか？

ビット操作のハック には、パフォーマンスや最適化に関する議論とともに、ビット操作のハックの素晴らしいコレクションがあります。そのサイトからの）あなたの問題に対する私のお気に入りのソリューションは、「乗算とルックアップ」です。

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];

参考になる文献

• " デ・ブルーイン配列を使ってコンピュータの単語の1をインデックス化する " - 上記のコードが動作する理由についての説明。
• " ボード表現 > Bitboards > BitScan " - この問題の詳細な分析、特にチェス・プログラミングに重点を置いたもの