C++でビット単位XORの結果が偶数になるペアをカウントする方法

整数型の配列が与えられ、その配列の要素から組み合わせられるすべてのペアのうち、ビット単位XOR演算の結果が偶数になるペアの総数を数えることが本記事の課題です。

XOR演算の真理値表

まず、XOR演算の基本的な挙動を理解するために、真理値表を確認しておきましょう。

この表から重要な性質が読み取れます。XOR演算の結果が奇数になるのは、片方の値が偶数でもう片方が奇数の場合だけです。両方とも偶数、または両方とも奇数の場合、XORの結果は必ず偶数になります。この性質こそが、効率的な解法の鍵となります。

入力例と出力例

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

出力 − XOR演算の結果が偶数になるペアの数：4

計算過程の詳細

配列 {2, 8, 1, 5, 11} から作れる全10通りのペアと、それぞれのXOR演算の結果は以下の通りです。

この中でXORの結果が偶数になっているのは、(2, 8) → 10、(1, 5) → 4、(1, 11) → 10、(5, 11) → 14 の4組です。したがって、答えは4となります。

プログラムで使用するアプローチ

• ペアを作成する対象となる整数要素の配列を入力として受け取る
• 配列のサイズを計算し、そのデータを関数に渡して処理を行う
• 配列内の奇数の要素数を格納するための一時変数 count を用意する
• i を 0 から配列のサイズまでループさせる
• ループ内で、arr[i] % 2 != 0（つまり要素が奇数）であれば count を1増やす
• temp を size * (size - 1) に設定する
• 別の一時変数 pairs を temp / 2 に設定する（これが全ペア数）
• 偶数と奇数が混ざるペアの数を count * (size - count) として計算する（この種のペアのXORは必ず奇数になる）
• XORが偶数になるペアの数を「全ペア数 − 奇数になるペア数」として求める
• 結果を返し、出力する

この方法を使えば、すべてのペアを実際に列挙して調べる O(n²) の素朴な手法と比べ、O(n) の時間計算量で答えを求められるため、大きな配列でも高速に処理できます。

サンプルコード

#include <iostream>
using namespace std;
//ビット単位XORが偶数になるペアを数える関数
int XOR_Even(int arr[], int size){
    int count = 0;
    for (int i = 0; i < size; i++){
        if (arr[i] % 2 != 0){
            count++;
        }
    }
    int temp = size * (size-1);
    int Pairs = temp / 2;
    int odd = count * (size - count);
    int even = Pairs - odd;
    return even;
}
int main(){
    int arr[] = { 2, 6, 1, 8};
    int size = sizeof(arr) / sizeof(arr[0]);
    cout<<"Count of pairs with Bitwise XOR as EVEN number are: "<<XOR_Even(arr, size);
    return 0;
}

出力

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

Count of pairs with Bitwise XOR as EVEN number are: 3

この例では、配列 {2, 6, 1, 8} の中で奇数は「1」の1個だけです。全ペア数は 4 × 3 ÷ 2 = 6、偶数と奇数が混ざるペアは 1 × 3 = 3 なので、XORが偶数になるペアは 6 − 3 = 3 と正しく計算されています。