题面：
在给定的 \(N\) 个整数 \(A1，A2……AN\) 中选出两个进行 \(xor\)（异或）运算，得到的结果最大是多少？
原题链接：143. 最大异或对 - AcWing
-
什么是异或？
1、相同为 \(0\)，不同为 \(1\)；
2、\(0\) 和任意数字进行异或，结果为数字本身。 -
为什么该题采用二叉字典树？
整数可以转化为32位字符串，通过字典树遍历所有路径。 -
什么时候考虑位运算？
1、状态压缩时可以利用二进制的每一位数表示01状态集合；[1]
2、判断某个数字是否只出现一次；
3、不用加减乘除实现加减法；
4、……
#include <bits/stdc++.h>
using namespace std;
const int N = 100010;
int n, ans, a[N];
int son[N * 32][2], idx;
void insert(int x) {
int p = 0;
//一个数最多 2^31 位
for (int i = 30; i >= 0; i--) {
int c = x >> i & 1; //提取二进制最末
if (!son[p][c])
son[p][c] = ++idx;
p = son[p][c];
}
}
int query(int x) {
int p = 0, res = 0;
for (int i = 30; i >= 0; i--) {
int c = x >> i & 1;
if (son[p][c ^ 1]) { //与当前位相反的异或最大
p = son[p][c ^ 1];
res = res * 2 + 1; //异或为1
}
else {
p = son[p][c]; //没有与当前位相反的路径
res *= 2; //异或为0
}
}
return res;
}
int main()
{
cin >> n;
for (int i = 0; i < n; i++) {
cin >> a[i];
insert(a[i]);
ans = max(ans, query(a[i]));
}
cout << ans;
}