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

このチュートリアルでは、C++を使って数値のパリティ（偶奇性）を効率的に求めるプログラムを作成します。

パリティとは、数値を2進数で表したときに「1」が現れる回数が偶数か奇数かを示すものです。通常、1ビットずつ確認する方法では計算に時間がかかりますが、XOR（排他的論理和）と右シフト演算子を組み合わせることで、わずか数ステップで高速に求められます。

パリティを求めるアルゴリズム

以下の手順で、XORと右シフト演算を繰り返し適用することで、32ビット整数のパリティを効率的に計算できます。

int b;
b = n ^ (n >> 1);
b = b ^ (b >> 2);
b = b ^ (b >> 4);
b = b ^ (b >> 8);
b = b ^ (b >> 16);

この処理により、すべてのビットの情報が最下位ビットに集約されます。最終的な結果の最下位ビットが 0 であれば偶数パリティ、1 であれば奇数パリティであると判定できます。

実装例

それでは、実際のコードを見てみましょう。

#include <bits/stdc++.h>
using namespace std;

void findParity(int n) {
    int b;
    b = n ^ (n >> 1);
    b = b ^ (b >> 2);
    b = b ^ (b >> 4);
    b = b ^ (b >> 8);
    b = b ^ (b >> 16);

    if ((b & 1) == 0) {
        cout << "Even Parity" << endl; // 偶数パリティ
    }
    else {
        cout << "Odd Parity" << endl;  // 奇数パリティ
    }
}

int main() {
    int n = 15;
    findParity(n);
    return 0;
}

実行結果

上記のコードを実行すると、次のような出力が得られます。

Even Parity

この例では入力値が 15（2進数で 1111）であり、「1」が4個、つまり偶数個含まれているため、結果は「偶数パリティ」となります。

まとめ

XORと右シフトを組み合わせた手法を使えば、ビットごとのカウントを行うことなく、定数時間でパリティを判定できます。組み込みシステムや通信分野での誤り検出など、パフォーマンスが求められる場面で特に有効なテクニックです。チュートリアルについて質問がある場合は、コメント欄でお気軽にお尋ねください。