最大异或对

题目

在给定的N个整数A1，A2……AN中选出两个进行xor（异或）运算，得到的结果最大是多少？
输入格式
第一行输入一个整数N。
第二行输入N个整数A1～AN。
输出格式
输出一个整数表示答案。
数据范围
1≤N≤105,0≤Ai<231
输入样例：
3
1 2 3
输出样例：
3

分析

异或也叫不进位加法。可以把每个数转换为31的二进制数，如果想要异或和最大，首先要先从高位考虑，如果找a的异或和，先要从高位找哪一个数的数位与a的相反，如果a的最高位是0，那就要找最高位是1的，如果没有就看次高位，然后依次一位一位的比较下去，最后可以发现其实是一个0 1二叉树

代码

#include<iostream>
#include<algorithm>
using namespace std;
const int N=100009;
int aa[N],trie[31*N][2],idx;

void insert(int x)
{
    int p=0;
    for(int i=30;i>=0;i--)
    {
        int u=x>>i&1;
        if(!trie[p][u]) trie[p][u]=++idx;
        p=trie[p][u];
    }
}

int query(int x)
{
    int p=0,res=0;
    for(int i=30;i>=0;i--)
    {
        int u=x>>i&1;  //判断第i位的数是0还是1
        if(trie[p][!u])//如果trie树中存储了！u，那么异或之后就是 1，res加上就行 
        {
            res+=1<<i;
            p=trie[p][!u];
        }
        else    p=trie[p][u];//如果没有！u，那么异或之后就是0，就没必要加
    }
    return res;
}

int main()
{
    int n;int ans=-1;
    cin>>n;
    for(int i=0;i<n;i++)  cin>>aa[i];
    for(int i=0;i<n;i++)
    {
        insert(aa[i]);
        ans=max(ans,query(aa[i]));
    }
    cout<<ans<<endl;
    return 0;
}