0

私はCでビットベクトルを扱っています.私unsigned long longのビットベクトルは. 多数のベクトルについて、パリティ、つまり 1 であるビットの数が偶数か奇数かを知る必要があります。

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

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

void checkIntersection(unsigned long long int setA, unsigned long long int setB){
    if(isEven(setA & setB)){
        //do something
    }
}
4

3 に答える 3

3

分割統治法を使用すると、次のようになります。

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) レジスタに組み込まれた並列ルックアップ テーブルを提供できるため、除算を停止するもう 1 つの良い点になります。または、単に 256 エントリの LUT の潜在的なキャッシュ ミスによって、1 ラウンド余分に計算タスクが過負荷になる可能性があります。当然のことながら、特定のアーキテクチャで最適な LUT サイズを測定するのが最善です。

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

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

上記のマジック定数のビットNは、 Parity(N)のブール値をエンコードします。

于 2014-02-27T08:26:39.420 に答える
1

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

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;
}

免責事項: 私はコードをテストしていません。これは単なるアイデアです。

于 2014-02-27T08:25:41.217 に答える