3

長整数 (64 ビット) で単一ビット インデックスを見つけるための最適なコードを見つけようとしています。長整数には、正確に 1 つのセット ビットがあります。(C言語使用)

現在、全体を 1 ビットシフトしてから、ゼロをチェックしています。ルックアップ テーブルについて読んだことがありますが、64 ビット全体には対応していません。ルックアップを使用しない場合は、各 8 ビットをゼロでチェックすることを考えましたが、それでも一度に 8 ずつシフトする必要があります。(1 8 回シフトするよりも 8 シフトする方が良い?)

(注: 私はモバイル デバイス用に開発していますが、[驚くことではありませんが] 遅いです)。

4

3 に答える 3

5

ビットを操作する方法が必要なときはいつでも、Bit Twiddling Hacksを探します。あなたの問題に対する解決策もほとんどありません。

このソリューションは、高速で最も高度なようです。

右側の連続する 0 ビット (末尾) を並列にカウントします。

unsigned int v;      // 32-bit word input to count zero bits on right
unsigned int c = 32; // c will be the number of zero bits on the right
v &= -signed(v);
if (v) c--;
if (v & 0x0000FFFF) c -= 16;
if (v & 0x00FF00FF) c -= 8;
if (v & 0x0F0F0F0F) c -= 4;
if (v & 0x33333333) c -= 2;
if (v & 0x55555555) c -= 1;

操作の数は、おおよそ N ビット ワードに対して、最大で 3 * lg(N) + 4 です。

于 2013-02-21T08:57:16.707 に答える
5

設定されているビットのバイナリ検索を実行できます。

int bitn(unsigned long long x)
{
    int n = 0;

    if (x >> 32) {
        n += 32;
        x >>= 32;
    }
    if (x >> 16) {
        n += 16;
        x >>= 16;
    }
    if (x >> 8) {
        n += 8;
        x >>= 8;
    }
    if (x >> 4) {
        n += 4;
        x >>= 4;
    }
    if (x >> 2) {
        n += 2;
        x >>= 2;
    }
    if (x >> 1) {
        n += 1;
    }

    return n;
}

GCC は、__builtin_ctzll()この機能を実行するビルトイン を提供します (これは、ハードウェアがこれを迅速に実行するために必要な特別な機能を利用します)。

于 2013-02-21T09:01:26.037 に答える
4

この提案 (およびここに示されている他の提案) を現在のコードと照らし合わせて確認する必要があります。ビットシフトが最も効率的な方法であるか、読みやすさを最適化する必要がある場合は違いがごくわずかであることがわかる場合があります。

いずれにせよ、これは高速であることが保証されているものではなく、試してベンチマークするものと考えてください。

可能な値は 64 個しかないため、次のようなものを使用できます。

int getSetBit (unsigned long x) {
    if (x == 0x8000000000000000UL) return 63;
    if (x == 0x4000000000000000UL) return 62;
    if (x == 0x2000000000000000UL) return 61;
    if (x == 0x1000000000000000UL) return 60;
    if (x == 0x0800000000000000UL) return 59;
    if (x == 0x0400000000000000UL) return 58;
    :
    if (x == 0x0000000000000002UL) return  1;
                                   return  0;
}

その方が高速であることに気付くかもしれませんが、ソリューションは通常、標準の範囲外の多くのもの (最適化戦略、データ キャッシング、パイプラインなど) の影響を受けます。

標準 C から離れることを厭わない場合、多くの環境には、次のような使用できる最適化されたものがありますgcc。

int __builtin_ffs (unsigned int x)
// Returns one plus the index of the least significant
//   1-bit of x, or if x is zero, returns zero.

もちろん、その場合、longを 2 つのintタイプに分割し、それぞれを個別に確認する必要がある場合があります (テストされていませんが、一般的なアイデアを得る必要があります)。

if (x < 0x80000000UL) return __builtin_ffs((unsigned int)x) - 1;
return __builtin_ffs((unsigned int)(x>>32)) -1 + 32;

または、からの出力を__builtin_clzl()操作してビット位置を取得することもできます (先頭のゼロ カウントが得られます) unsigned long。ここでgccビルトインを見ることができます。

于 2013-02-21T08:54:50.493 に答える