最大异或对(trie树)

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

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

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

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

数据范围
1≤N≤105,
0≤Ai<231
输入样例：
3
1 2 3
输出样例：
3

#include<iostream> using namespace std; const int N = 3000000;//一个数最多有30位二进制数*数据范围，防止越界 int a[N],n; int idx;//节点下标 int son[N][2]; void insert(int x){     int p = 0;     for(int i=30;i>=0;i--){         int u = x>>i&1;//&1可以取出右移之后的最后一位         if(!son[p][u]) son[p][u] = ++idx;         p = son[p][u];     } } int query(int x){     int p = 0;     int res = 0;     for(int i=30;i>=0;i--)     {         int u = x>>i&1;         if(son[p][!u]){             res += 1<<i;             //res是异或后最大的答案 不是与x相异的最大数，             //如果进入if (son[p][!s])这个语句时，             //说明当前位置两个数不同异或完的结果是1，             //进else的话异或完结果就是0，不需要加到答案res里。             p = son[p][!u];         }         else             p = son[p][u];     }     return res; } int main(){     cin>>n;     for(int i=0;i<n;i++)     {         cin>>a[i];         insert(a[i]);     }     int res = 0;     for(int i=0;i<n;i++)         res = max(res, query(a[i]));     cout<<res<<endl;     return 0; }