C++でビット単位ORの結果が偶数になるペアを数える方法

整数型の配列が与えられたとき、その要素から作れるすべてのペアのうち、ビット単位のOR演算の結果が偶数になるペアが何組あるかを数えるのが本記事のテーマです。

結論から言うと、OR演算の結果が偶数になるのは、2つの数がどちらも偶数である場合だけです。この性質を利用すれば、全ペアを実際に計算しなくても、配列内の偶数の個数を数えて組み合わせの数を求めるだけで答えが得られます。

OR演算の真理値表

OR演算では、2つの入力のどちらか一方でも1であれば結果は1になります。

なぜ「両方が偶数」のときだけ偶数になるのか

数の偶奇は最下位ビット（LSB）で決まります。OR演算では、最下位ビット同士の演算結果がそのまま結果の偶奇を決めます。0 | 0 = 0（偶数）となる「両方が偶数」のケース以外は、必ず最下位ビットが1になるため、結果は奇数になります。

入力例と実行結果

入力 − int arr[] = {2, 5, 1, 8, 9}

出力 − ビット単位ORが偶数になるペアの数：1

説明 − 配列から作れるすべてのペアとOR演算の結果は以下の通りです。

この中でORの結果が偶数になっているのは (2, 8) の1組だけです。これは「偶数の要素が2個（2と8）含まれており、その組み合わせは C(2,2) = 1」という計算結果と一致します。

アルゴリズムの手順

• ペアを作る対象となる整数型の配列を受け取る
• 配列のサイズを求め、処理用の関数にデータを渡す
• 偶数の要素数を記録するための一時変数 count を用意する
• i を 0 から配列サイズまで FOR ループで回す
• ループ内で arr[i] & 1 == FALSE（最下位ビットが0＝偶数）なら count を1増やす
• count を count * (count - 1) / 2 に更新する（nC2 = n×(n−1)/2 の公式）
• count を返す
• 結果を出力する

C++サンプルコード

#include <iostream>
using namespace std;
// ビット単位ORが偶数になるペアを数える関数
int count_pair(int arr[], int size){
    int count = 0;
    for (int i = 0; i < size; i++){
        if (!(arr[i] & 1)){
            count++;
        }
    }
    count = count * (count - 1) / 2;
    return count;
}
int main(){
    int arr[] = {2, 5, 1, 8, 9, 2, 7};
    int size = sizeof(arr) / sizeof(arr[0]);
    cout << "ビット単位ORが偶数になるペアの数: " << count_pair(arr, size) << endl;
    return 0;
}

出力

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

ビット単位ORが偶数になるペアの数: 3

この例では配列 {2, 5, 1, 8, 9, 2, 7} に偶数が3個（2, 8, 2）含まれているため、C(3,2) = 3 という結果になります。

計算量について

この手法は配列を一度走査するだけでよいため、時間計算量は O(n)、追加のメモリも定数で済み、空間計算量は O(1) です。すべてのペアを総当たりで確認する O(n²) の素朴な方法と比べて、大幅に効率的である点が大きなメリットです。