c++ - x=2^k の左端の 1 ビットのインデックスを見つける方法は?

Question

重複の可能性:
ビットをカウントするための効率的なビット単位の操作、または右または左のほとんどのものを見つける

検索アルゴリズムを書きました。32bit intそれを最適化するために、番号0〜31を使用できるかどうかをマークするために使用したいと思います。つまり、 state がある場合State、次を使用して可能なすべての数値を簡単に取得できます。

x = State & -State
State -= x

しかし、実際には、1 in がどこにあるかを知る必要があります(のバイナリ形式xには 1 しかないことに注意してください)。x例えばの場合x = 0000 0100、それが 3 番目であることを知りたいです。

ループを使えばできることはわかっていforますが、時間がかかりそうです。

ビット単位の操作を使用する方法があるのだろうか？そして、static_cast<int>(log2(x))多くの時間がかかりますか？

助けてくれてありがとう。

score 3 · Accepted Answer

2 のすべてのべき乗に対して巨大なスイッチを使用するという明白な解決策については誰も言及していないようです。

以下のコードは、これに加えて、二分探索と 2 による除算を実装しています。

注: これらの関数は、入力が 2 のべき乗であることを想定しています。そうでない場合、ナンセンスを返す可能性があります。

#include <inttypes.h>
#include <stdio.h>

int get_exp_switch (uint64_t x)
{
    switch (x) {
        case (uint64_t)1 << 0: return 0;
        case (uint64_t)1 << 1: return 1;
        case (uint64_t)1 << 2: return 2;
        case (uint64_t)1 << 3: return 3;
        case (uint64_t)1 << 4: return 4;
        case (uint64_t)1 << 5: return 5;
        case (uint64_t)1 << 6: return 6;
        case (uint64_t)1 << 7: return 7;
        case (uint64_t)1 << 8: return 8;
        case (uint64_t)1 << 9: return 9;
        case (uint64_t)1 << 10: return 10;
        case (uint64_t)1 << 11: return 11;
        case (uint64_t)1 << 12: return 12;
        case (uint64_t)1 << 13: return 13;
        case (uint64_t)1 << 14: return 14;
        case (uint64_t)1 << 15: return 15;
        case (uint64_t)1 << 16: return 16;
        case (uint64_t)1 << 17: return 17;
        case (uint64_t)1 << 18: return 18;
        case (uint64_t)1 << 19: return 19;
        case (uint64_t)1 << 20: return 20;
        case (uint64_t)1 << 21: return 21;
        case (uint64_t)1 << 22: return 22;
        case (uint64_t)1 << 23: return 23;
        case (uint64_t)1 << 24: return 24;
        case (uint64_t)1 << 25: return 25;
        case (uint64_t)1 << 26: return 26;
        case (uint64_t)1 << 27: return 27;
        case (uint64_t)1 << 28: return 28;
        case (uint64_t)1 << 29: return 29;
        case (uint64_t)1 << 30: return 30;
        case (uint64_t)1 << 31: return 31;
        case (uint64_t)1 << 32: return 32;
        case (uint64_t)1 << 33: return 33;
        case (uint64_t)1 << 34: return 34;
        case (uint64_t)1 << 35: return 35;
        case (uint64_t)1 << 36: return 36;
        case (uint64_t)1 << 37: return 37;
        case (uint64_t)1 << 38: return 38;
        case (uint64_t)1 << 39: return 39;
        case (uint64_t)1 << 40: return 40;
        case (uint64_t)1 << 41: return 41;
        case (uint64_t)1 << 42: return 42;
        case (uint64_t)1 << 43: return 43;
        case (uint64_t)1 << 44: return 44;
        case (uint64_t)1 << 45: return 45;
        case (uint64_t)1 << 46: return 46;
        case (uint64_t)1 << 47: return 47;
        case (uint64_t)1 << 48: return 48;
        case (uint64_t)1 << 49: return 49;
        case (uint64_t)1 << 50: return 50;
        case (uint64_t)1 << 51: return 51;
        case (uint64_t)1 << 52: return 52;
        case (uint64_t)1 << 53: return 53;
        case (uint64_t)1 << 54: return 54;
        case (uint64_t)1 << 55: return 55;
        case (uint64_t)1 << 56: return 56;
        case (uint64_t)1 << 57: return 57;
        case (uint64_t)1 << 58: return 58;
        case (uint64_t)1 << 59: return 59;
        case (uint64_t)1 << 60: return 60;
        case (uint64_t)1 << 61: return 61;
        case (uint64_t)1 << 62: return 62;
        case (uint64_t)1 << 63: return 63;
        default: return 0; // not allowed
    }
}

int get_exp_simple (uint64_t x)
{
    int i = -1;
    do {
        i++;
        x /= 2;
    } while (x > 0);
    return i;
}

int get_exp_binsearch (uint64_t x)
{
    int left = 63;
    int right = 0;

    while (left > right) {
        int middle = (left + right) / 2;
        uint64_t middle_value = (uint64_t)1 << middle;
        if (x < middle_value) {
            left = middle - 1;
        }
        else if (x > middle_value) {
            right = middle + 1;
        }
        else {
            return middle;
        }
    }

    return left;
}

int main ()
{
    uint64_t sum = 0;

    for (int j = 0; j < 100000; j++) {
        for (int i = 0; i < 64; i++) {
            uint64_t x = (uint64_t)1 << i;
            int l = get_exp_switch(x);
            //int l = get_exp_simple(x);
            //int l = get_exp_binsearch(x);
            sum += l;
            //printf("%" PRIu64 ": %d\n", x, l);
        }
    }

    printf("%" PRIu64 "\n", sum);

    return 0;
}

私の（64ビット）システムでのベンチマーク結果clang -O2：

get_exp_switch: 0m0.103s
get_exp_simple: 0m0.196s
get_exp_binsearch: 0m0.158s

ただし、より大きな整数 (bignum) を使用すると、二分探索法はすぐに単純な方法よりも優れたパフォーマンスを発揮し始め、switch メソッドのコードサイズが容認できないほど大きくなる可能性があることに注意してください。

score 3 · Accepted Answer

CTZ多くの CPU には、 (「末尾のゼロを数えてください」)のようなネイティブのハードウェア命令があります。GCC は組み込み関数を通じてこれを公開します __builtin_ctz。他のコンパイラにも同様の機能が必要です。

score 1 · Accepted Answer

ビット単位の演算子を使用する必要がある場合は、ここからビットスキャンのトリックを使用できますが、ほとんどのコンパイラには、最初/最後のセットビットを見つけるための組み込み関数 (別名 BitScanForward および BitScanReverse) があり、これらの関数は最新のプロセッサでは非常に高速であり、使用する必要があります (技術的には、これらはビット単位の操作です。つまり、ビットを操作しますが、演算子形式はありません)。

score 0 · Accepted Answer

log（n）検索を実行できます（疑似cコード、試したことはありませんが、機能するはずです。nは位置と同じです）。

STATE = 0010 0000
int bits=8;

int n=1;
while(bits>1)
{
    bits >>=1;//right shift 1
    int upper = STATE>>bits; //get the upper half
    if(upper)
    {
        n+=bits;
        STATE>>=bits;
    }
    //else the "1" is on the right side
}

事前に作成されたテーブルでルックアップを実行することもできます。上記のループを実行します（32ビットテーブルはおそらくスペーススペースが多すぎるため）が、（たとえば）bits == 4のときに停止し、16バイト長のルックアップテーブルでルックアップを実行します（その数をに追加します'n'）。

c++ - x=2^k の左端の 1 ビットのインデックスを見つける方法は?

4 に答える 4

Related

Reference