0

64ビットビットマスクで設定されたすべてのビット位置を識別する最良の方法は何ですか. 私のビット マスクが 0xDeadBeefDeadBeef であると仮定すると、設定されたビットのすべてのビット位置を識別するための最良の方法は何でしょうか。

long long bit_mask = 0xdeadbeefdeadbeef;
unsigned int bit_pos=0;
while(mask) {
  if((mask&1)==1) {
     printf("Set bit position is:%d \n",bit_pos};
  }
  bit_pos++;
  mask>>=1; 
}

1 つの方法は、それをループして、ビットが設定されているかどうかを確認し、設定されている場合は、カウント位置を返し、MSB までループを続けることです。したがって、64 ビットの場合は、設定されたすべてのビットをトラバースするまで繰り返します。または、MSB が設定されている場合は 64 ビットすべてがトラバースされますが、それを行うためのより良い方法があるはずですか?

4

5 に答える 5

1

すでに説明した素敵なちょっといじるハックに加えて、他のオプションがあります。

これは、x86(64)、SSE4、gcc があり、使用できる -msse4 スイッチでコンパイルすることを前提としています。

int CountOnesSSE4(unsigned int x)
{
    return __builtin_popcount(x);
}

これは単一の popcnt 命令にコンパイルされます。高速なコードが必要な場合は、実際に実行時に SSE をチェックし、利用可能な最適な機能を使用できます。

数値が 1 の数が少ないと予想される場合、これも高速になる可能性があります (通常のシフトおよび比較ループよりも常に高速です)。

int CountOnes(unsigned int x)
{
    int cnt = 0;
    while (x) {
        x >>= ffs(x);
        cnt++;
    }
    return cnt;
}

x86 では (SSE がなくても) ffs は単一の命令 (bsf) にコンパイルされ、ループの数は 1 の数に依存します。

于 2013-10-15T06:56:44.850 に答える
0

数を数えている場合は、高速なハッカーズ デライト ソリューションを使用できますが、ルックアップ テーブルの方が高速になる場合があります (常にそうとは限りません)。そして、はるかに理解できます。たとえば、バイト値 0x00 から 0xFF のカウントを表す 256 項目の深さのテーブルを事前に準備できます。

0, //0x00
1, //0x01
1, //0x02
2, //0x03
1, //0x04
2, //0x05
2, //0x06
3, //0x07
...

そのテーブルを構築するためのコードは、すべてのビット アプローチを通じて低速のステップを使用する可能性があります。

構築したら、より大きな数をバイトに分割できます

count  = table8[number&0xFF]; number>>=8;
count += table8[number&0xFF]; number>>=8;
count += table8[number&0xFF]; number>>=8;
count += table8[number&0xFF]; number>>=8;
...

より多くのメモリがある場合は、0x0000 から 0xFFFF までの数値に対して 65536 の深さのテーブルで、より広い数値を表すことによって、テーブルをさらに大きくすることができます。

count  = table16[number&0xFFFF]; number>>16;
count += table16[number&0xFFFF]; number>>16;
count += table16[number&0xFFFF]; number>>16;
count += table16[number&0xFFFF]; number>>16;

テーブルは、メモリ消費を犠牲にしてこのようなことを高速化するための一般的な方法です。消費できるメモリが多いほど、リアルタイム計算ではなく、事前計算 (コンパイル時またはコンパイル時前) の量が多くなります。

于 2013-10-15T12:56:51.643 に答える