C++で2つの配列の各要素同士の最大XORを求める方法

この記事では、n個の要素を持つ2つの配列AとBが与えられたとき、配列Aの各要素について配列Bのどの要素と組み合わせればXORが最大になるかを求めるプログラムをC++で作成します。

つまり、配列Aの各要素ごとに、配列Bの中からXOR値が最も大きくなる相手を選び出すのが課題です。

問題の例

具体例を使って問題を理解しましょう。

入力：

array A = {3, 6, 11, 9}
array B = {8, 2, 4, 1}

出力：

11 14 15 13

説明：

配列Aの各要素と配列Bのすべての要素とのXORの組み合わせを計算し、それぞれの最大値を選択します。

3 XOR 8 = 11   3 XOR 2 = 1   3 XOR 4 = 7   3 XOR 1 = 2    → 最大値：11
6 XOR 8 = 14   6 XOR 2 = 4   6 XOR 4 = 2   6 XOR 1 = 1    → 最大値：14
11 XOR 8 = 3   11 XOR 2 = 9   11 XOR 4 = 15   11 XOR 1 = 10    → 最大値：15
9 XOR 8 = 1   9 XOR 2 = 11   9 XOR 4 = 13   9 XOR 1 = 8    → 最大値：13

解き方のアプローチ

1. 単純な解法（計算量 O(n²)）

最もシンプルな方法は、上記の例のようにすべての組み合わせを総当たりで計算し、最大のXORを出力することです。しかし、この方法は二重ループに依存するため、計算量がO(n²)となり、データ数が多い場合には非効率になります。

2. トライ（Trie）を使った効率的な解法

そこで、トライ（Trie）データ構造を活用したより効率的な解法を紹介します。トライに配列Bの全要素を2進数のビット列として格納し、配列Aの各要素との照合を行うことで最大XORを求めます。

具体的には、配列Aの各要素について最上位ビット（MSB）から順に確認し、XORの結果が1になるように「現在のビットの反対」の分岐を選択しながら辿っていきます。これを下位のビットまで繰り返すことで、各要素に対する最大XORの相手を効率よく見つけることができます。この手法により、計算量を要素数×ビット長（約32回の比較）程度まで抑えられます。

C++での実装例

以下は、配列Aの各要素と配列Bとの間で可能な最大XORを求めるプログラムです。

#include<iostream>
using namespace std;
struct trie{
    int value;
    trie *child[2];
};
trie * get(){
    trie * root = new trie;
    root -> value = 0;
    root -> child[0] = NULL;
    root -> child[1] = NULL;
    return root;
}
void insert(trie * root, int key){
    trie * temp = root;
    for (int i = 31; i >= 0; i--){
        bool current_bit = key & (1 << i);
        if (temp -> child[current_bit] == NULL)
            temp -> child[current_bit] = get();
        temp = temp -> child[current_bit];
    }
    temp -> value = key;
}
int findMaxXor(trie * root, int element){
    trie * temp = root;
    for (int i = 31; i >= 0; i--){
        bool bits = ( element & ( 1 << i) );
        if (temp -> child[1 - bits] != NULL)
            temp = temp -> child[1 - bits];
        else
            temp = temp -> child[bits];
    }
    return (element ^ temp -> value);
}
int main(){
    int A[] = {3, 11, 6, 9};
    int B[] = {8, 2, 4, 1};
    int N = sizeof(A)/sizeof(A[0]);
    trie * root = get();
    for (int i = 0; i < N; i++)
    insert(root, B[i]);
    cout<<"The maximum possible XOR of every possible element in array A with Array B is\n";
    for (int i = 0; i < N; i++)
    cout <<findMaxXor(root, A[i])<<"\t";
    return 0;
}

出力結果

The maximum possible XOR of every possible element in array A with Array B is
11 15 14 13