1

非常に大きなビットベクトル（つまり、100,000ビット）に設定されているビットをカウントしたいと思います。

私が現在行っているのは、charへのポインター（つまり、char * cPtr）を使用して、ビット配列の先頭を指すことです。そして私は・・・それから私は： 

1. look at each element of the array (i.e. cPtr[x]),   
2. convert it to an integer (i.e. (int) cPtr[x])   
3. use a 256 element look-up table to see how many bits are set in the given byte (i.e. cPtr[x]).

代わりにshortintポインター（つまり、short int * sPtr）を使用すると、ルックアップの数は半分になりますが、65534要素のルックアップテーブルを使用すると、独自のコストが発生します。メモリ使用量。

毎回調べるのに最適なビット数はいくつなのか気になります。また、その数値がプリセットタイプのサイズではない場合、ビットベクトルをたどって、ビット配列の開始位置を超えた任意のビット数にポインタを設定するにはどうすればよいですか。

ビットをカウントする方法は他にもあることは知っていますが、今のところ、他の方法と比較する前に、この方法を最適化できることを確認したいと思います。

4

4 に答える 4

2

ビット演算を使用してカウントできます。

char c = cPtr[x];
int num = ((c & 0x01) >> 0) +
          ((c & 0x02) >> 1) +
          ((c & 0x04) >> 2) +
          ((c & 0x08) >> 3) +
          ((c & 0x10) >> 4) +
          ((c & 0x20) >> 5) +
          ((c & 0x40) >> 6) +
          ((c & 0x80) >> 7);

少し長いように思えるかもしれませんが、メモリに何度もアクセスする必要がないので、結局のところ、かなり安いように思えます。

毎回intを読み取ることでさらに安くすることもできますが、その場合はおそらく配置の問題に対処する必要があります。

于 2012-03-05T21:22:19.050 に答える
1

これは非常に高速である必要があります（ウィキペディアから取得）：

static unsigned char wordbits[65536] = { bitcounts of ints between 0 and 65535 };
static int popcount(uint32 i)
{
    return (wordbits[i&0xFFFF] + wordbits[i>>16]);
}

このようにして、反復ごとに32ビットをチェックできます。

于 2012-03-05T21:22:33.760 に答える
1

毎回調べるのに最適なビット数はいくつですか？

見つける唯一の方法はテストすることです。一度に32ビットをカウントする最速の方法については、この質問を参照してください。

また、その数値がプリセットタイプのサイズではない場合、ビットベクトルをたどって、ビット配列の開始位置を超えた任意のビット数にポインタを設定するにはどうすればよいですか。

任意のビットへのポインタを設定することはできません。ほとんどのマシンにはバイトアドレス指定があり、一部のマシンはワードのみをアドレス指定できます。

次のように、任意のビットで始まる単語を作成できます。

long wordAtBit(int32_t* array, size_t bit)
{
    size_t idx = bit>>5;
    long word = array[idx] >> (bit&31);
    return word | (array[idx+1] << (32 - (bit&31));
}
于 2012-03-05T21:58:49.680 に答える
0

私はパーティーに少し遅れていますが、これまでに提案されたものよりもはるかに速いアプローチがあります。その理由は、多くの最新のアーキテクチャがさまざまな方法でビット数をカウントするハードウェア命令を提供しているためです（先行ゼロ、先行ゼロ、後続ゼロまたは1、1に設定されたビット数のカウントなど）。1に設定されたビット数をカウントすることは、ハミング重みと呼ばれ、一般に人口カウントまたは単にポップカウントとも呼ばれます。

実際のところ、x86 CPUには、SSE4.2命令セットの一部としてPOPCNT命令があります。Intelの最新のCPUアーキテクチャ（Haswellと呼ばれる）は、BMI1およびBMI2拡張機能を使用したビット操作のためのさらに多くのハードウェアサポートを提供します-おそらくそこで使用するものが他にあります！

于 2013-08-18T21:30:56.503 に答える