C++でビット単位XORが奇数になるペアを数える方法

整数型の配列が与えられたとき、その配列の要素から組み合わせられるすべてのペアの中で、ビット単位XOR（排他的論理和）を計算した結果が奇数となるペアの総数を求めるのがこの問題の目的です。

XOR演算の真理値表

まずは、XOR演算の基本的な挙動を真理値表で確認しましょう。

この表からわかるように、XORの結果が1（奇数）になるのは、2つの値のうち片方だけが1（奇数）である場合です。言い換えると、「偶数と奇数」の組み合わせでのみXORは奇数になり、偶数同士や奇数同士の組み合わせでは必ず偶数になります。

入力例と出力例

• 入力 − int arr[] = {2, 8, 1, 5, 11}
• 出力 − XORが奇数になるペアの総数：6

全ペアの検証

上記の10通りの組み合わせのうち、XORの結果が奇数（3、7、9、9、13、3）になっているのは6通りです。これは、配列中の偶数（2、8）が2個、奇数（1、5、11）が3個あるため、「2 × 3 = 6」という計算結果と一致します。

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

すべてのペアを実際に計算するとO(n²)の時間がかかりますが、前述の性質を利用すれば、偶数の個数を数えるだけで答えをO(n)で求められます。手順は以下のとおりです。

• 整数要素の配列を入力として受け取り、ペアを形成できるようにします。
• 配列のサイズを計算し、後続の処理のためにデータを関数へ渡します。
• 偶数の個数を格納するための一時変数countを用意します。
• iを0から配列サイズまでループさせ、各要素が偶数（arr[i] % 2 == 0）であればcountをインクリメントします。
• 奇数の個数は「size - count」で求められるため、XORが奇数になるペアの総数は count * (size - count) で計算できます。
• 結果を返して出力します。

C++実装例

#include <iostream>
using namespace std;
//XORが奇数になるペアを数える
int XOR_Odd(int arr[], int size){
    int count = 0;
    for (int i = 0; i < size; i++){
        if (arr[i] % 2 == 0){
            count++;
        }
    }
    int odd = count * (size-count);
    return odd;
}
int main(){
    int arr[] = { 6, 1, 3, 4, 8, 9};
    int size = sizeof(arr) / sizeof(arr[0]);
    cout<<"XORが奇数になるペアの総数: "<<XOR_Odd(arr, size);
    return 0;
}

出力結果

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

XORが奇数になるペアの総数: 9

この配列{6, 1, 3, 4, 8, 9}には偶数が3個（6、4、8）、奇数が3個（1、3、9）含まれているため、3 × 3 = 9という結果になります。全ペアを総当たりで調べる必要がないため、配列のサイズが大きくなっても高速に処理できる点がこの手法の大きな利点です。