题目描述

在给定的N个整数A1，A2……AN中选出两个进行xor（异或）运算，得到的结果最大是多少？

输入格式
第一行输入一个整数N。

第二行输入N个整数A1～AN。

输出格式
输出一个整数表示答案。

数据范围
1≤N≤105,
0≤Ai<231

样例

输入样例：
3
1 2 3
输出样例：
3

算法1

C++ 代码

#include<bits/stdc++.h>
using namespace std;
const int N = 100010, M = N * 30;
int n, a[N], son[M][2], res, idx;
void add(int x)
{
    int p = 0;
    for(int i = 30; i >= 0; i --)
    {
        int &s = son[p][x >> i & 1];
        if(!s) s = ++ idx;
        p = s;
    }
}
int query(int x)
{
    int p = 0, ans = 0;
    for(int i = 30; i >= 0; i --)
    {
        int s = x >> i & 1;
        if(son[p][!s])
        {
            ans += 1 << i;
            p = son[p][!s];
        }
        else p = son[p][s];
    }
    return ans;
}
int main()
{
    cin >> n;
    for(int i = 0; i < n; i ++) cin >> a[i], add(a[i]);
    for(int i = 0; i < n; i ++) res = max(res, query(a[i]));
    cout << res << endl;
    return 0;
}