经典问题---最大异或对

项目场景：

最大异或对问题的解决。

异或：在计算机中数都是由二进制组成的 异或是二进制之间的一种计算规则。

每一位计算 相同为0 不同为1 对应数字电路中的异或门。

如 6 ^5

6: 110

5: 101

结果：011 为 3

问题描述

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

输入格式

第一行输入一个整数 N。

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

输出格式

输出一个整数表示答案。

数据范围

1≤N≤105,
0≤Ai<231

输入样例：

3
1 2 3

输出样例：

3

原因分析：

解决方案：

暴力算法：

#include<iostream>
#include<algorithm>
using namespace std;
const int N =100010;
int a[N];

int main(){
    int n;
    cin>>n;
    for(int i=0;i<n;i++) cin>>a[i];
    int res=0;
    for(int i=0;i<n;i++)
        for(int j =0 ;j<n;j++)
            res = max(res,a[i]^a[j]);

    cout<<res<<endl;

    return 0;

}

优化后的Trie树算法：
 

#include<iostream>
#include<algorithm>
using namespace std;
const int N =100010;
const int M =31*N;
int idx,son[M][2],n;
int a[N];

//定义插入函数
void insert(int x){
    int p=0;
    for(int i=30;~i;i--){
        //从高到低获取当前位数上的值 0 or 1
        int u = x >> i & 1;
        //如果当前节点的子节点不存在时 则创建节点
        if(!son[p][u]){
            //idx表示当前节点 idx++ 表示移动到下一个节点
            son[p][u] = ++idx;
        }
        //相当于链表中让当前节点指向下一个节点
        p = son[p][u];
        
    }
}

//定义查询函数
int query(int x){
    //res表示要返回的值 也就是存在的与查询元素x异或后的最大值
    int p=0,res =0;
    for(int i=30;~i;i--){
        //从高到低获取当前位数上的值 0 or 1
        int u = x>>i &1;
        
        //如果当前节点的子节点与查询元素的相反的元素存在 则皆大欢喜 沿着该路径前进
        if(son[p][!u]) {
            p = son[p][!u];
            res = res *2 +!u;
        }
         //如果当前节点的子节点与查询元素的相反的元素不存在 则选择存在的路径
        else{
            p = son[p][u];
            res = res *2 +u;
        }
    }
    return res;
}

int main(){
    cin>>n;
    for(int i=0;i<n;i++) scanf("%d",&a[i]);
    
    int res =0;
    for(int i=0;i<n;i++){
        //先插入再查询是为了避免特判边界情况 一开始trie树中没有元素
        insert(a[i]);
        int t = query(a[i]);
        res = max(res,t^a[i]);
    }
    cout<<res<<endl;
    return 0;
}