GCCは、Haswellが指定されていない限り、先行ゼロカウントをコンパイルしません。

Question

GCCは、の先行ゼロの数を0からまで数えます（__builtin_clz(int x)組み込み）。 とりわけ

が、これはを切り捨て、効率的xの2を底とする対数を取るlg(unsigned int x)機能を実装するための素晴らしいです：

/** return the base-2 log of x, where x > 0 */ 
unsigned lg(unsigned x) { 
    return 31U - (unsigned)__builtin_clz(x); 
} 

これは簡単な方法で動作します - 特にケースを考えると、x == 1とclz(x) == 31-次にx == 2^0だからlg(x) == 0と31 - 31 == 0となり、正しい結果が得られます。 xの高い値も同様に機能します。

組み込み関数が効率的に実装されていると仮定すると、これは代わりのpure C solutionsよりはるかに優れています。

先行ゼロのカウントは、の操作は本質的にx86のbsr命令のデュアルです。これは、引数の中で最も重要な1ビットのインデックスを返します。したがって、先行する10個のゼロがある場合、最初の1ビットは引数のビット21にあります。一般に我々は31 - clz(x) == bsr(x)を有し、そのようにbsr実際にはのは、余分な31U - ...部分を除いて、所望のlg()機能を実装する。

実際には、線の間に読み込まれ、__builtin_clz機能を念頭に置いてbsrで実施されたことを見ることができます：それは未定義の動作として定義される引数がゼロ、もちろん「先行ゼロ」の操作がある場合ゼロ引数を持つ32（またはintのビットサイズが何であれ）として完全に定義されています。したがって、__builtin_clzは、x86上のbsr命令に効率的にマップされるという考えで確実に実装されました。

しかし、どのようなGCCを見て、実際にそうでない場合は、デフォルトのオプションで-O3で、行います。それadds a ton of extra junk：

xor edi,31ラインを効果的に実際問題として、それがオフすることによってです下の4ビット分のnot ediある

lg(unsigned int): 
     bsr  edi, edi 
     mov  eax, 31 
     xor  edi, 31 
     sub  eax, edi 
     ret 

-one neg edibsrの結果はclzになります。次に31 - clz(x)が実行されます。しかし-mtune=haswellと

、正確に予想単一bsr命令にcode simplifies：それはケースをなぜ

lg(unsigned int): 
     bsr  eax, edi 
     ret 

は、私にとって非常に不明瞭です。 bsr命令はHaswellの前に数十年前から行われており、AFAIKの動作は変更されていません。bsr +余分な命令の束は、普通よりも高速ではないでしょうbsrさらに遅いコードでは-mtune=haswellstill resultsを使用していますので、特定のアーチに対してチューニングの問題だけではありません。

64ビット入力と出力のための状況がeven slightly worse次のとおりです。余分なmovsxはclzからの結果が負になることはありませんので、何もしないように思われるクリティカルパスにあります。ここでも、-march=haswellバリアントは単一のbsr命令で最適です。

最後に、Windows以外のコンパイラ空間の大手プレーヤーicc and clangを確認しましょう。 iccちょうど良い仕事をし、neg eax; add eax, 31; neg eax; add eax, 31; - wtfのような冗長なものを追加しますか？ は、-marchに関係なく良い仕事をします。このような第1の組のビットのためのビットマップを走査するよう

---

。

0の対数はundefinitedあり、そのため0引数で私たちの関数を呼び出すことは未定義の動作です。

ここで、LSBは0番目のビットで、MSBは31番目です。

を2の補数で呼び出す。これはGCCの既知の問題のように見えます

Answer 1

：https://gcc.gnu.org/bugzilla/show_bug.cgi?id=50168