题目描述
在给定的N个整数A1,A2……AN中选出两个进行xor(异或)运算,得到的结果最大是多少?
输入格式
第一行输入一个整数N。
第二行输入N个整数A1~AN。
输出格式
输出一个整数表示答案。
数据范围
1≤N≤105,
0≤Ai<231
输入样例:
3
1 2 3
输出样例:
3
Java代码
import java.util.Scanner;
public class Main{
static int N = 100010, M = 3000000; //一共是N个数字,每个数字循环31次 = 3100000
static int[][] son = new int[M][2]; //当前节点的子节点,第一维表示trie的长度,第二维表示每个节点只会有两个子节点
static int idx = 1,res = 0; //root节点为空,所以从1开始存储
public static void main(String[] args){
Scanner in = new Scanner(System.in);
int n = in.nextInt();
int[] a = new int[N];
for(int i = 0; i < n; i ++) //初始化数组
{
a[i] = in.nextInt();
insert(a[i]);
}
for(int i = 0; i < n; i ++){
res = Math.max(res,query(a[i]));
}
System.out.print(res);
}
private static void insert(int a)
{
int p = 0; //p代表当前节点
for(int i = 30; i >= 0; i --) //数据的范围是0≤Ai<2e31,所以我们每次循环31次就够了,也就是0~30
{
int s = a >> i & 1; //位运算的一个公式,求二进制数的第k位数是多少
if(son[p][s] == 0) son[p][s] = idx++;
p = son[p][s]; //把当前节点移动到下一个节点
}
}
private static int query(int a){
int p = 0,res = 0;
for(int i = 30; i >= 0; i --)
{
int s = a >> i & 1;
if(son[p][1-s] != 0){ //1-s表示与高位不同的路,比如说s=0,1-0=1; s=1,1-1=0; 恰好相反
res += (1 << i); //左移1等价于乘以2; res把每一位*2加起来就是10进制了
p = son[p][1-s]; //如果有和高位不同的数字,那么就走这一条路
} else p = son[p][s];
}
return res;
}
}