Bitvectorの計算パリティを知るための高速な方法

StackOverflow https://stackoverflow.com//questions/22062709

  •  23-12-2019
  •  | 
  •  

質問

私はcでbitvectorsを使って作業しています。私のbitvectorsは次のとおりです unsigned long long's.多数のベクトルについては、パリティ、つまり1であるビット数は、偶数または奇数です。

正確な値は重要ではなく、パリティだけです。私は、ものの数を計算してチェックするよりも速いものがあるかどうか疑問に思っていました。私は何かを考えようとしましたが、何も見つかりませんでした。

これをどのように機能させたいかの短い例:

void checkIntersection(unsigned long long int setA, unsigned long long int setB){
    if(isEven(setA & setB)){
        //do something
    }
}
役に立ちましたか？

解決

分割と征服のテクニックを使って:

uint64_t a = value;
a ^= (a >> 32);            // Fold the 32 MSB over the 32 LSB
a ^= (a >> 16);            // reducing the problem by 50%
a ^= (a >> 8);             // <-- this can be a good break even point
..
return lookup_table[a & 0xff];  // 16 or 256 entries are typically good
..

折りたたみ手順は最後まで適用することができます:

a ^= (a >> 1);
return a & 1;

IAでは、パリティフラグは8ビットに縮小した後に直接取得することができます。

a ^= (a >> 4); 一部のプロセッサアーキテクチャでは並列ルックアップテーブルを提供できるため、分割を停止する別の良い点になります uint8_t LUT[16] XXM（またはNEON）レジスタに埋め込まれています。または、単純に256エントリのLUTの潜在的なキャッシュミスは、1つの余分なラウンドの計算タスクを単純に過体重にすることができます。どのlutサイズが特定のアーキテクチャで最適かを測定するのが当然のことです。

この最後のテーブルは実際には16ビットのみで構成され、シーケンスでエミュレートできます:

return ((TRUTH_TABLE_FOR_PARITY) >> (a & 15)) & 1;

ここでビット N 上記の魔法定数のブール値をエンコードします パリティ(N).

他のヒント

バイト内のビットのすべての可能な組み合わせのすべての可能なすべての組み合わせのパリティを配列で事前計算することができました：

bool pre[256] = { 0, 1, 1, 0, 1, ....}
.

大規模な配列のパリティを見つける必要があるときは、

bool parity (long long unsigned x)
{   
    bool parity = 0;
    while(x)
    {   
        parity ^= pre[x&0xff];
        x>>=8;
    }
    return parity;
}
.

免責事項：コードをテストしていない、それは単なる考えです。

かなり簡単です。

のようなもの 
unsigned population(unsigned long long x) {
  x = ((x >> 1) & 0x5555555555555555) + (x & 0x5555555555555555);
  x = ((x >> 2) & 0x3333333333333333) + (x & 0x3333333333333333);
  x = ((x >> 4) & 0x0f0f0f0f0f0f0f0f) + (x & 0x0f0f0f0f0f0f0f0f);
  x = (x >> 8) + x;  // Don't need to mask, because 64 < 0xff
  x = (x >> 16) + x;
  x = (x >> 32) + x;
  return x & 0xff;
}
.

仕事が必要です。また、CPUの中には人口数の指示があります（私はx86はしないとは思わない）。

この種のことが好きなら、あなたはHenry S. Warren、Jr。

で本をチェックする必要があります。

ライセンス： CC-BY-SA と 帰属
所属していません StackOverflow
scroll top