最大异或对

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

输入格式

第一行输入一个整数 N。

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

输出格式

输出一个整数表示答案。

数据范围

1≤N≤105
0≤Ai<2^31-1

输入样例:

3
1 2 3

输出样例:

3

#include<iostream>
using namespace std;
const int N=100010;
int a[N];
int son[N*35][2];
int n,idx;
int res;
void insert(int x)
{
    int p=0;
    for(int i=30;~i;--i)
    {
        int u=(x>>i)&1;
        if(!son[p][u]) son[p][u]=++idx;
        p=son[p][u];
    }
}
int query(int x)
{
    int res=0;
    int p=0;
    for(int i=30;~i;--i)
    {
        int u=(x>>i)&1;
        if(son[p][!u])
        {
            res+=1<<i;
            p=son[p][!u];
        }
        else p=son[p][u];
    }
    return res;
}
int main()
{
    cin>>n;
    for(int i=1;i<=n;++i)
    {
        scanf("%d",&a[i]);
        insert(a[i]);
    }
    for(int i=1;i<=n;++i) res=max(res,query(a[i]));
    cout<<res<<endl;
    return 0;
}