セットされる最下位ビットの位置

Bit Twiddling Hacks は、パフォーマンス/最適化の議論が添付された、えーと、少しいじるハックの優れたコレクションを提供します。あなたの問題に対する私のお気に入りの解決策 (そのサイトから) は、«乗算と検索» です:

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

参考資料:

  • "Using de Bruijn Sequences to Index a 1 in a Computer Word" - 上記のコードが機能する理由の説明
  • "Board Representation> Bitboards> BitScan" - チェス プログラミングに特に焦点を当てた、この問題の詳細な分析

組み込みの ffs を使用しないのはなぜですか? (Linux から man ページを取得しましたが、それよりも広く利用できます。)


x86 アセンブリ命令 (bsf) があります。 )それはそれを行います。 :)

より最適化?!

補足:

このレベルでの最適化は、本質的にアーキテクチャに依存します。今日のプロセッサは複雑すぎる (分岐予測、キャッシュ ミス、パイプライン処理に関して) どのコードがどのアーキテクチャでより速く実行されるかを予測することは非常に困難です。オペレーションを 32 から 9 に減らすなど、一部のアーキテクチャではパフォーマンスが低下することさえあります。 1 つのアーキテクチャで最適化されたコードは、他のアーキテクチャではより悪いコードになる可能性があります。これを特定の CPU 用に最適化するか、そのままにして、コンパイラーがより良いと判断するものを選択できるようにするかのどちらかだと思います。