18

Cプログラミングで32ビットの符号なし整数の先行ゼロの数を数える効率的なアルゴリズムは何ですか?

4

3 に答える 3

25

この説明は、コンパイラが操作をサポートしていないか、十分なアセンブリを生成しないことを前提としています。これらの両方が最近ではありそうもないので__builtin_clz、コンパイラで gcc または同等のものを使用することをお勧めします。

どの clz アルゴリズムが「最適」かを判断できるのは、あなただけです。最新のプロセッサは複雑な獣であり、これらのアルゴリズムのパフォーマンスは、それを実行するプラットフォーム、それに投入するデータ、およびそれを使用するコードに大きく依存します. 確実にする唯一の方法は、測定、測定、さらに測定することです。違いがわからない場合は、おそらくボトルネックを見ていない可能性があり、他の場所に時間を費やしたほうがよいでしょう。

退屈な免責事項が邪魔にならないようになったので、Hacker's Delightがこの問題について何と言っているかを見てみましょう。簡単な調査では、すべてのアルゴリズムが何らかの記述の二分探索に依存していることがわかります。簡単な例を次に示します。

int n = 32;
unsigned y;

y = x >>16; if (y != 0) { n = n -16; x = y; }
y = x >> 8; if (y != 0) { n = n - 8; x = y; }
y = x >> 4; if (y != 0) { n = n - 4; x = y; }
y = x >> 2; if (y != 0) { n = n - 2; x = y; }
y = x >> 1; if (y != 0) return n - 2;
return n - x;

これは 32 個の int で機能し、必要に応じて反復バージョンに変換できることに注意してください。残念ながら、このソリューションには命令レベルの並列処理が十分に行われておらず、かなりの数の分岐があり、非常に優れたいじり回しアルゴリズムにはなりません。上記のコードのブランチ フリー バージョンが存在することに注意してください。ただし、はるかに冗長であるため、ここでは再現しません。

それでは、pop 命令 (ビット数をカウントする) を使用してソリューションを改善しましょう。

x = x | (x >> 1);
x = x | (x >> 2);
x = x | (x >> 4);
x = x | (x >> 8);
x = x | (x >>16);
return pop(~x);

では、これはどのように機能するのでしょうか。キーは、pop(~x)のゼロの数を数える最後の命令xです。ゼロの数を意味のあるものにするには、先頭にないすべての 0 を最初に取り除く必要があります。これを行うには、バイナリ アルゴリズムを使用して 1 を正しく伝播します。命令レベルの並列性はまだあまりありませんが、すべての分岐を取り除き、以前のソリューションよりも使用するサイクルが少なくなりました。ずっといい。

では、そのポップな指示はどうですか、それは不正行為ではありませんか? ほとんどのアーキテクチャには、コンパイラのビルトイン (gcc など) を介してアクセスできる 1 サイクルの pop 命令があります__builtin_pop。それ以外の場合は、テーブル ベースのソリューションが存在しますが、テーブルが完全に L1 キャッシュに保持されている場合でも、キャッシュ アクセスのサイクルをトレードオフする場合は注意が必要です。

最後に、ハッカーの喜びとしていつものように、私たちは奇妙な領域をさまよい始めます。浮動小数点数を使用して先行ゼロをいくつか数えてみましょう。

union {
    unsigned asInt[2];
    double asDouble;
};
asDouble = (double)k + 0.5;
return 1054 - (asInt[LE] >> 20);

まず、ちょっとした警告: DON'T USE THIS ALGORITHM . これは、標準に関する限り、未定義の動作を引き起こします。これは、実際の用途よりも楽しい要素のために再現されました。自己責任で使用してください。

免責事項が邪魔にならなくなったので、それはどのように機能しますか? 最初に int を double に変換し、続いて double の指数コンポーネントを抽出します。きちんとしたもの。LE 定数は、リトル エンディアン マシンで実行する場合は 1、ビッグ エンディアン マシンで実行する場合は 0 にする必要があります。

これにより、この問題に対するさまざまなビット調整アルゴリズムの簡単な調査が得られるはずです。この本にはこれらのいくつかのバリエーションがあり、さまざまなトレードオフがありますが、それらを自分で発見できるようにします.

于 2014-05-25T15:43:43.030 に答える
-3

先行ゼロでない桁数を数えましょう。その後は (32 - n) を実行するだけです。まず、数値がゼロの場合、n はゼロです。さもないと：

n = 1 + floor(log2(x))

つまり、2 を底とする対数を使用して、ゼロ以外の最上位ビットがどの位置にあるかを調べます。これは、log2 を計算する FYL2X 命令を使用して x86 で効率的に実行できます。

しかし、今は x86 命令について話しているので、実際に利用できるものを見てみましょう。ここにあります！http://en.wikipedia.org/wiki/Find_first_set - アセンブリを記述したい場合、または少なくとも最適化コンパイラがこれらの命令を生成することを確認したい場合は、必要なことを直接実行する命令がたくさんあることがわかります。慎重に書かれたCコードが与えられたからです。

于 2014-05-25T15:11:33.627 に答える