☰

C で整数の最上位ビット (msb) を見つける最も高速で効率的な方法は何ですか? 質問する

tag-icon • tag-icon c algorithm optimization bit-manipulation
C で整数の最上位ビット (msb) を見つける最も高速で効率的な方法は何ですか? 質問する

ある整数 がありn、最上位ビットの位置を知りたい場合（つまり、最下位ビットが右側にある場合は、 である最も左端のビットの位置を知りたい場合1）、最も速く効率的に調べる方法は何ですか？

ffs()POSIX では最初に設定されたビットを見つけるためのメソッドがサポートされていることは知っています<strings.h>が、対応するメソッドはないようですfls()。

私が見逃している、これを行うための非常に明白な方法はありますか?

移植性のために POSIX 関数を使用できない場合はどうでしょうか?

編集: 32 ビット アーキテクチャと 64 ビット アーキテクチャの両方で動作するソリューションはどうでしょうか (コード リストの多くは 32 ビット整数でのみ動作するように見えます)。

ベストアンサー1

GCCは:

-- 組み込み関数: int __builtin_clz (unsigned int x)
     Xの先頭の0ビットの数を返します。
     有効ビット位置。X が 0 の場合、結果は未定義になります。

 -- 組み込み関数: int __builtin_clzl (unsigned long)
     `__builtin_clz' に似ていますが、引数の型が `unsigned
     長さ'。

 -- 組み込み関数: int __builtin_clzll (unsigned long long)
     `__builtin_clz' に似ていますが、引数の型が `unsigned
     長い長い'。

これらは、複雑なビット操作アルゴリズムの 1 つであろうと、単一の命令であろうと、現在のプラットフォームにとってかなり効率的なものに変換されるものと期待しています。

入力した内容ができるがゼロになるのは__builtin_clz(x | 1)、他のビットを変更せずに無条件に下位ビットを設定すると、他の入力の出力は変更されずに、31の出力が作成されるためです。x=0

それを実行する必要がないようにするには、他のオプションとして、ARM GCC __clz(ヘッダーは不要) などのプラットフォーム固有の組み込み関数、または命令_lzcnt_u32をサポートする CPU 上のx86 をlzcnt使用します。(古い CPU では、エラーが発生するのではなくlzcntとしてデコードされるbsrため、非ゼロ入力に対して 31-lzcnt が返されることに注意してください。)

残念ながら、input=0 の結果を 32 または 64 (オペランドの幅に応じて) と定義する x86 以外のプラットフォームでは、さまざまな CLZ 命令を移植可能に利用する方法はありません。x86 でもlzcnt同じことが行われますが、bsrを使用しない限り、コンパイラが反転する必要があるビット インデックスが生成されます31-__builtin_clz(x)。

（「未定義の結果」はCの未定義の動作ではなく、単に定義されていない値です。これは実際には命令が実行されたときに宛先レジスタにあったものです。AMDはこれを文書化していますが、Intelは文書化していませんが、IntelのCPUはその動作を実装しています。しかし、ない割り当てるC変数に以前何があったとしても、gccがCをasmに変換するときには通常はそうはなりません。LZCNT の「出力依存性」を打破することがなぜ重要なのでしょうか?）

おすすめ記事