C++で同じインデックスの要素を除いた配列全体のXORから新しい配列を構築する方法

n個の正の整数で構成される配列A[]があるとします。このとき、B[i]が「A[i]以外のすべての要素のXOR」となるような別の配列Bを作成することを考えます。

例えば、A = [2, 1, 5, 9] の場合、結果は B = [13, 14, 10, 6] となります。

• B[0] = 1 ^ 5 ^ 9 = 13
• B[1] = 2 ^ 5 ^ 9 = 14
• B[2] = 2 ^ 1 ^ 9 = 10
• B[3] = 2 ^ 1 ^ 5 = 6

解法のアプローチ

この問題を効率的に解く鍵となるのは、XORの重要な性質「a ^ a = 0（同じ値同士のXORは0になる）」です。手順は以下の通りです。

1. まず、配列Aの全要素のXORを計算し、変数xに格納します。
2. 次に、各要素A[i]に対して、B[i] = x ^ A[i] を計算します。

xには配列全体のXORが格納されているため、x ^ A[i] を計算するとA[i]同士が打ち消し合い、結果として「A[i]以外の全要素のXOR」が得られます。各要素ごとに残りの要素をループで回す素朴なO(n²)の手法と比べ、この方法ならO(n)という高速な処理が実現できる点が大きなメリットです。

サンプルコード（C++）

#include <iostream>
using namespace std;

void findXOR(int A[], int n) {
    int x = 0;
    // 全要素のXORを計算
    for (int i = 0; i < n; i++)
        x ^= A[i];
    // 各要素を「全体のXOR ^ 自身」で置き換え
    for (int i = 0; i < n; i++)
        A[i] = x ^ A[i];
}

int main() {
    int A[] = {2, 1, 5, 9};
    int n = sizeof(A) / sizeof(A[0]);
    cout << "Actual elements: ";
    for (int i = 0; i < n; i++)
        cout << A[i] << " ";
    cout << endl;
    cout << "After XOR elements: ";
    findXOR(A, n);
    for (int i = 0; i < n; i++)
        cout << A[i] << " ";
}

出力結果

Actual elements: 2 1 5 9
After XOR elements: 13 14 10 6

まとめ

XORの自己打ち消しの性質を利用すれば、「自分以外の全要素のXOR」を求める問題をわずか2回のループで解決できます。計算量はO(n)、追加のメモリも変数1つだけで済むため、非常に効率的なアルゴリズムと言えます。ビット演算の性質を活かした定番テクニックなので、競技プログラミングなどでもぜひ覚えておきたい方法です。