数値のパリティチェック|2進数の1の個数から偶数・奇数を判定する方法

パリティとは

数値のパリティは、その数値を2進数に変換したときに含まれる「1」の個数によって決まります。「1」の個数が奇数であれば奇数パリティ、偶数であれば偶数パリティと判定されます。

コンピュータのメモリ上では、数値はすべて2進数として格納されているため、ビットシフト操作を使えば簡単に各ビットを調べることができます。この記事では、ビットを右へシフトしながら、与えられた数値の2進表現に含まれる「1」の個数を数え、パリティを求める方法を解説します。

入力と出力

入力:
数値: 5
2進数表現は (101)

出力:
5 のパリティは 奇数 です。

アルゴリズム

findParity(n)

入力: 判定対象の数値 n。
出力: その数値が偶数パリティか奇数パリティかの結果。

Begin
    count := 0
    temp := n

    while temp >= 2, do
       if temp の LSb(最下位ビット)が 1 ならば
           count := count + 1
       temp を 1 ビット右シフトする
    done

    if count が奇数ならば
       奇数パリティと表示
    else
       偶数パリティと表示
End

手順の解説

1. カウンタ変数 count を 0 で初期化し、temp に n を代入します。
2. temp が 2 以上である間、最下位ビット(LSb)が 1 であれば count を 1 増やします。
3. temp を 1 ビット右シフトし、すべてのビットを確認できるまで繰り返します。
4. ループ終了後、count が奇数なら「奇数パリティ」、偶数なら「偶数パリティ」と判定します。

C++による実装例

#include <iostream>
using namespace std;

bool findParity(int n) {
    int count = 0;
    int temp = n;

    while (temp>=2) {
        if(temp & 1)    // 最下位ビットが 1 の場合、カウントを増やす
            count++;
        temp = temp >> 1;    // 数値を 1 ビット右シフトする
    }
    return (count % 2)?true:false;
}

int main() {
    int n;
    cout << "Enter a number: "; cin >>n;
    cout << "Parity of " << n << " is " << (findParity(n)?"Odd":"Even");
}

実行結果

Enter a number: 5
Parity of 5 is Odd

補足: より効率的な方法

上記の実装では、ビット長の分だけループを回す必要があります。一方、Brian Kernighan のアルゴリズムを利用すると、「n & (n-1)」という演算で最下位にある 1 を順番に消去していけるため、ループ回数は「1」の個数分だけで済みます。大きな数値を扱う場合には、この手法の方が高速にパリティを求められるので覚えておくと便利です。