C++で数値のパリティを効率的に求める方法を解説

パリティとは

この記事では、与えられた数値Nのパリティを求めるC++プログラムについて解説します。

パリティとは、数値を2進数で表したときに含まれる「1」の個数（セットビット数）を指します。

2進表現における「1」の個数が偶数であれば「偶数パリティ（Even Parity）」、奇数であれば「奇数パリティ（Odd Parity）」と呼ばれます。

効率的なアルゴリズム

与えられた数値をNとするとき、以下の手順で演算を行うことで、パリティを高速に求めることができます。

• y = N ^ (N >> 1)
• y = y ^ (y >> 2)
• y = y ^ (y >> 4)
• y = y ^ (y >> 8)
• y = y ^ (y >> 16)

これらの演算をすべて実行した後、yの最下位ビット（右端のビット）がその数値のパリティを表します。最下位ビットが1であれば奇数パリティ、0であれば偶数パリティとなります。

この手法は「XOR畳み込み」と呼ばれるテクニックで、上位ビットと下位ビットを16ビット→8ビット→4ビット→2ビット→1ビットと段階的に折りたたむことで、32ビット整数のパリティをわずか5回のシフト演算とXOR演算で計算できます。ビットを1つずつ数える方法と比較して、処理速度が大幅に向上するのが特徴です。

サンプルコード

#include <bits/stdc++.h>
using namespace std;
bool calc_parity(int N) {
    int y;
    y = N ^ (N >> 1);
    y = y ^ (y >> 2);
    y = y ^ (y >> 4);
    y = y ^ (y >> 8);
    y = y ^ (y >> 16);
    // 最下位ビットの確認
    if (y & 1)
        return 1;
    return 0;
}
int main() {
    int n = 1345;
    int result = calc_parity(n);
    if (result == 1)
        cout << "Odd Parity" << endl;
    else
        cout << "Even Parity" << endl;
    return 0;
}

実行結果

Even Parity

この例では、n = 1345（2進数で「10101000001」）に含まれる「1」の個数は4個（偶数）であるため、「Even Parity（偶数パリティ）」が出力されます。