C++で配列内のすべてのペアのXORの合計を求める方法

この問題では、n個の整数からなる配列 arr[] が与えられます。配列内のすべてのペアについてXORを計算し、その合計を求めるプログラムを作成することが課題です。

問題を理解するための例

入力: arr[] = {5, 1, 4}
出力: 10
説明: すべてのペアのXOR:
5 ^ 1 = 4
1 ^ 4 = 5
5 ^ 4 = 1
合計 = 4 + 5 + 1 = 10

解法1: 全ペアを列挙する素朴なアプローチ

最もシンプルな解き方は、ネストされたループを使って配列内のすべてのペアを列挙する方法です。各ペアのXORを計算し、それを順次合計に加算していきます。

アルゴリズム

sum = 0 で初期化
ステップ1: i を 0 から n-1 までループ:
　　ステップ1.1: j を i+1 から n-1 までループ:
　　　　ステップ1.1.1: sum を更新 → sum += arr[i] ^ arr[j]
ステップ2: sum を返す。

実装例

上記の解法の動作を示すプログラムは以下の通りです。

#include <iostream>
using namespace std;
int findXORSum(int arr[], int n) {
    int sum = 0;
    for (int i = 0; i < n; i++)
        for (int j = i + 1; j < n; j++)
            sum += (arr[i]^arr[j]);
    return sum;
}
int main() {
    int arr[] = { 5, 1, 4 };
    int n = sizeof(arr) / sizeof(arr[0]);
    cout<<"配列内のすべてのペアのXORの合計は "<<findXORSum(arr, n);
    return 0;
}

出力

配列内のすべてのペアのXORの合計は 10

このアルゴリズムの時間計算量は O(n²) であり、要素数が大きくなると非効率になる可能性があります。

解法2: ビット操作を用いた効率的なアプローチ

より効率的な解法として、ビット操作のテクニックを利用する方法があります。

ここでは、各数値をビット単位で捉え、それぞれのビット位置ごとに以下の式を適用して中間的な合計を求めます。

(セットされているビットの数) × (セットされていないビットの数) × (2^(ビット位置))

最終的な合計を求めるには、すべてのビット位置について得られた中間和を足し合わせます。

この手法が正しく機能する理由は、あるビット位置でのXORが1になるのは、そのビットが片方の数だけセットされている場合、つまり「セットされているビット」と「セットされていないビット」の組み合わせのときだけだからです。したがって、setBits × unsetBits 個のペアがそのビット位置で合計に寄与することになります。

なお、この解法では64ビット整数を想定しているため、あらかじめ扱うビット数が必要となります。

アルゴリズム

sum = 0、setBits = 0、unsetBits = 0 で初期化。
ステップ1: i を 0 から 64 までループし、ステップ2・3を繰り返す。
ステップ2: setBits と unsetBits を 0 にリセット。
ステップ3: 配列の各要素について、i 番目のビット位置における setBits と unsetBits の値を求める。
ステップ4: sum += (setBits * unsetBits * (2^i)) で更新。

実装例

上記の解法の動作を示すプログラムは以下の通りです。

#include <iostream>
#include <math.h>
using namespace std;
long findXORSum(int arr[], int n) {
    long sum = 0;
    int unsetBits = 0, setBits = 0;
    for (int i = 0; i < 32; i++) {
        unsetBits = 0; setBits = 0;
        for (int j = 0; j < n; j++) {
            if (arr[j] % 2 == 0)
                unsetBits++;
            else
                setBits++;
            arr[j] /= 2;
        }
        sum += ( unsetBits*setBits* (pow(2,i)) );
    }
    return sum;
}
int main() {
    int arr[] = { 5, 1, 4, 7, 9};
    int n = sizeof(arr) / sizeof(arr[0]);
    cout<<"配列内のすべてのペアのXORの合計は "<<findXORSum(arr, n);
    return 0;
}

出力

配列内のすべてのペアのXORの合計は 68

このビット操作ベースの手法では、時間計算量が O(n × ビット数) となり、全ペアを列挙する O(n²) のアプローチと比べて大幅に高速に処理できます。特に大きな配列を扱う場合に有効な最適化手法と言えるでしょう。