The XOR Largest Pair

在给定的N个整数 A_1,A_2,…,A_N中选出两个进行异或运算，得到的结果最大是多少？
Input
第一行一个整数N。
第二行N个整数 A_i
Output
一个整数表示答案。
Sample Input
5
2 9 5 7 0
Sample Output
14
HINT
1<= N<= 10^5, 0<= A_i <2^{31}

/*
此题数据范围有100000,N平方的枚举是过不了
考虑到只是做xor运算，于是可以将数字先全加入到trie中
(全部转成32位的二进制)
例如数字12转成二进制1100,从高位到低位加入trie
(因为我们如果希望ans尽可能大时，那么尽可能保证高位)
然后再查每个数字在trie中能走的最大路径
也就是说这个数字的当前位为1,就走0那边，反之亦然(在能走的情况下)
 
*/
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll a[100001];
int trie[3100001][2],tot,n;
void ins(ll v)
{
    int p=0;
    for(int i=31;i>=0;i--)
    {
        int l=(v>>i)&1;
       // cout<<"L is   "<<l<<endl;
        if(!trie[p][l])
		     trie[p][l]=++tot;
        p=trie[p][l];
    }
}
ll find(ll v)
{
    int p=0;
    ll sum=0;
    for(int i=31;i>=0;i--)
    {
        int l=(v>>i)&1;
        if(trie[p][l^1]) //如果存在与当前位相反的数字 
		   p=trie[p][l^1],sum=sum<<1|1; 
		   //sum=sum*2+1,因为所有数字左移了一位，则当前两个数字不相同，必然有1 
        else //否则就只能走与当前位相同值的那边了 
		     p=trie[p][l],sum=sum<<1;
		     //sum=sum*2
    }
    return sum;
}
int main()
{
    scanf("%d",&n);ll ans=0;
    for(int i=1;i<=n;i++)  //先将所有的数字加入到trie中 
	    scanf("%lld",&a[i]),ins(a[i]);
    for(int i=1;i<=n;i++) //再扫描一遍 
	    ans=max(ans,find(a[i]));
    printf("%lld
",ans);
}