C++で数値のパリティ（奇偶性）を求めるプログラム

このチュートリアルでは、C++を使って数値のパリティ（奇偶性）を求める方法について解説します。

パリティとは、ある数値を2進数で表したときに含まれる「1」の個数が、奇数であるか偶数であるかを指します。本記事では、入力として与えられた数値のパリティを効率的に判定するアルゴリズムを紹介します。

パリティの求め方

ここで紹介する手法では、ビット演算を活用します。ポイントとなるのは n & (n - 1) という式です。この式は、n の最下位にある「1」のビットを消去する働きがあります。この操作を n が 0 になるまで繰り返し、ループが回った回数（＝1のビットの個数）から奇偶を判定します。

C++での実装例

# include<bits/stdc++.h>
# define bool int
using namespace std;
// 与えられた数値のパリティを求める関数
bool getParity(unsigned int n) {
    bool parity = 0;
    while (n){
        parity = !parity;      // ビットを1つ処理するごとに反転
        n = n & (n - 1);       // 最下位の1ビットを消去
    }
    return parity;
}
int main() {
    unsigned int n = 7;
    cout<<"Parity of no "<<n<<": "<<(getParity(n)? "Odd": "even");
    getchar();
    return 0;
}

コードの解説

• parity = !parity; … 1のビットを1つ見つけるたびにフラグを反転させます。
• n = n & (n - 1); … Brian Kernighanのアルゴリズムと呼ばれる技法で、n の中で最も右側にある1のビットを取り除きます。
• ループは「1」の個数分だけしか回らないため、全ビットを走査する方法よりも高速です。

出力結果

上記のプログラムを実行すると、次のような結果が出力されます。

Parity of no 7: odd

数値7は2進数で 111 と表され、「1」が3つ（奇数個）含まれているため、パリティは「odd（奇数）」と判定されます。