5

重複の可能性：
ビットをカウントしたり、右|左端のビットを検索したりするための効率的なビット演算

（32ビット）2進数の最初の1を見つけるための高速な方法はありますか？

たとえば、番号が00000000 000000000000000010000000の場合

数値の最初のゼロが右から7番目のビットに格納されているため、値「7」（または反対側から読み取った場合は「24」）を計算したいと思います。

これを行うより速い方法はありますか

int pos=0;
int number = 127; //binary from above
while ((number>>pos) > 0) { pos++; }

？

おそらく、特定のx86アセンブラ命令ですか？

4

5 に答える 5

5

__builtin_ctzgccでは、とを使用できます__builtin_clz。 ctz末尾の0ビットclzの数を示し、先頭の0ビットの数を示します。

于 2012-11-20T15:59:32.023 に答える
3

はい、マクロを使用せずに、より高速な方法があります。

あなたの方法では、最大32*2の操作を行うことができます。

これが対数アルゴリズムです。

まず、番号を2つのショートパンツに分割し、下のショートパンツが0であることを確認します。0の場合、offset = 16を維持しながら、上位部分を確認します。0でない場合は、オフセット= 0で、下部を確認します。ショートとオフセットが残ります。

次に、残りの部分を2文字に分割し、同じように進めます。文字とオフセットが残ります。

次に、charを4ビットの2つの部分に分割し、同じことを確認します。

最大ログ32*2の操作を行います。

于 2012-11-20T16:09:51.197 に答える
3

x86のビットスキャン命令を探しています

__inline__ size_t bsf(size_t input) {
    size_t pos;
    __asm__ ("bsf %1, %0" : "=r" (pos) : "rm" (input));
    return pos;
}

インラインasmを使用する場合は、posとinputが同じストレージクラス（2、4、または8バイト整数型）であることを確認してください。このインライン関数は問題ありません。

ほとんどのコンパイラには、この命令を使用する組み込み関数がありますが、直接のものを持っているのはMSVCだけです。

最上位ビットセットの場合bsrは、代わりに同じ構文の命令を使用してください。

注：入力が0（ビットが設定されていない）の場合、結果は未定義です！

pos入力が0の場合に事前定義された定数を入れるバージョンは次のとおりです。

#define BIT_SCAN_IFZERO 0

__inline__ size_t bsf(size_t input) {
    size_t pos, ifzero = BIT_SCAN_IFZERO;
    __asm__ ( "bsf %1, %0\n\t"
              "cmovz %2, %0"
            : "=r" (pos)
            : "rm" (input)
            , "rm" (ifzero));
    return pos;
}

好きなように定義BIT_SCAN_IFZEROします。そこで負の数が必要な場合は、（符号付きサイズタイプ）に変更size_tしてくださいssize_t

于 2012-11-20T16:17:46.810 に答える
1

MSVC組み込み関数はと_BitScanForwardです_BitScanReverse。

ここでそれらの引数を調べることができます。それらは過度に直感的ではありません（必要な値は戻り値ではありません）。

于 2012-11-20T16:06:14.073 に答える
-2

それはそれを行うためのほとんど最速の方法です。複数の単語の可能性を扱っている場合は、最初の単語をテストしてから2番目の単語をテストし、0ではなく最も低い単語を見つけることができます。ただし、それでもシフトする必要があります。

于 2012-11-20T15:59:30.363 に答える