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

第一行一个整数 N。

第二行 N 个整数 Ai​​ 。

一个整数表示答案。

5
2 9 5 7 0

14

对于 100% 的数据，1≤N≤10^5,0≤Ai<2^31​​ 。

题目分析

本题是一道极其经典的算法面试与竞赛题，要求在一个长度为 N 的数组中，找出两个数字，使得它们的异或（XOR）结果最大。 数据范围给到了 N≤10^5，如果采用暴力的双重 for 循环两两匹配，时间复杂度是 O(N^2)，运算次数高达 10^10 级别，毫无悬念会超时。这就逼迫我们必须寻找一个 O(Nlog(maxA)) 级别的高效算法。

处理“最大异或值”问题的绝对标配，就是01字典树。

解题思路与思考过程

异或运算的核心法则是：相同为 0，不同为 1。 要想让异或得到的值尽量大，在二进制表示下，我们必须秉持一个极其贪心的策略：高位的 1 绝对比低位的 1 更重要。因此，当我们拿着一个数字 X 去找它的“最佳异偶”时，我们希望从它的最高位开始，每一位都尽量找和它相反的数。

思路演进：

1. 初级思维（字符串具象化）：最直观的想法是，把所有的整数像十进制转二进制那样，用 %2 和 /2 拆开，存进 vector，补齐前导 0 后拼接成 string，然后当成普通的英文字符串插入字典树。这种做法逻辑上是通的，也最符合人类的直觉思维。

2. 进阶思维（位运算）：在计算机底层，整数本身就是以 32 位二进制的形式静态躺在内存里的！我们根本不需要脱裤子放屁去借助 vector 和 string 拆解它。直接利用位运算 (x>>i)&1 就能在 1 个 CPU 时钟周期内，瞬间精准提取出我们要的第 i 位是 0 还是 1。

算法设计

1. 建树（Insert）：把数组中所有的数，从最高有效位（第 30 位）到最低位（第 0 位），依次取出其二进制的 0 或 1，插入到一棵只有两个分叉（0 通道和 1 通道）的字典树中。

2. 查询（Query）：拿着数字 X，同样从最高位开始在树上遍历。

   • 取出 X 的当前位 Y。我们极其渴望走与它相反的路径 Z=Yˆ1。

   • 如果字典树中 Z 路径存在（nxt[Z]!=0），果断走进去，并且让最终答案累加 2^i（因为这一位异或出了 1）。

   • 如果 Z 路径不存在，被逼无奈只能走相同的路径 Y。这一位异或结果为 0，答案不累加。

3. 统计：让数组里的每个数字都去树上跑一遍 query，维护全局最大值。

时空复杂度分析

• 时间复杂度：每个数字插入和查询都需要遍历 31 位。建树复杂度为 O(31×N)，查询复杂度为 O(31×N)。总体时间复杂度为 O(N)（严格来说是 O(Nlog(maxA))），面对 10^5 的数据，运算不过几百万次，速度极快。

• 空间复杂度：由于每个数字最多贡献 31 个节点，总节点数不会超过 31×10^5。采用静态数组 tree[4000000][2]，空间复杂度为 O(Nlog(maxA))，在正常内存限制内绝对安全。

坑点总结

1. pow 函数的精度刺客：使用 <cmath> 里的 pow(2,k) 计算 2 的次幂，返回的是浮点数。在位数较高时，极易因浮点精度丢失导致最终转成 int 时少 1。必须使用位运算 1<<k 来代替。

2. 字典树通道有效性判定：判断一个节点是否存在，是看它的 nxt 是否被分配过有效编号，即 nxt[v]!=0，不能写成 nxt[v]==1（这会导致只认第一个分配的节点，丢弃后续所有路径）。

3. 0 的边界死角：如果采用除 2 取余法拆解数字，遇到 x=0 时 while(x!=0) 会直接跳过，导致存入空串。位运算写法天然免疫此问题。

---

两个版本代码的区别与演进

下面展示这段代码的进化史。 版本一（普通字典树写法），把十进制转二进制、位数对齐补 0、反转拼接成字符串的逻辑强行闭环，非常直观，但由于频繁申请 vector 和 string 内存，常数极大，且存在 pow 精度风险。 版本二（纯位运算标程），剔除了所有多余的容器，直接操作底层二进制位，代码极度精简，执行效率是版本一的数十倍以上，属于竞赛必背的满分模板。

版本一：直观具象化写法（普通字典树思想）

//普通字典树写法 可以全部ac 但是常数开销大
#include <iostream>
#include <algorithm>//对应max函数
#include <cmath>//对应pow函数 算法竞赛中极不推荐用pow算2的次幂）
#include <vector>
using namespace std;
int n;
//a数组里每一行是一个vector，用来暂存每个数字拆解后的二进制位
//注意：由于是x%2拆解，存入的顺序是 从低位到高位
vector<int> a[100010];//存整数转换为二进制的结果
int sum;//计算最后异或结果的最大值


//字典树节点
struct treenode{
    //状态转移表：记录通往0和1两个方向的下一个节点编号（门牌号）
    //里面存的是整数编号，不能当成bool值来判断==1
    int nxt[2];
}tree[4000000];
int pc;//记录当前开辟到了第几个节点


//字典树插入(接受纯0/1组成的字符串)
void insert(string &s){
    int p=0;//每一轮从根节点开始
    int len=s.size();
    for(int i=0;i<len;i++){
        //如果该字符分支不存在 就开辟一个新空间给到它
        if(tree[p].nxt[s[i]-'0']==0) tree[p].nxt[s[i]-'0']=++pc;
        //更新指针位置 继续往下走
        p=tree[p].nxt[s[i]-'0'];
    }
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n;
    int len1=0;//存储所有整数转化为二进制后，最长的那个位数

    //先把所有整数转化为二进制数存起来
    //a里面每一行存的是每一个整数二进制表示下从低位到高位
    for(int i=1;i<=n;i++){
        int x;
        cin>>x;
        //先把x转换为二进制存储到a数组中
        while(x!=0){
            a[i].push_back(x%2);//剥离最后一位
            x=x/2;//右移一位
        }
        int len2=a[i].size();
        //更新最大二进制位数
        len1=max(len1,len2);
    }

    //接下来把每个整数位数不足len1的都在最后补0（最高位）
    for(int i=1;i<=n;i++){
        //当前整数总位数
        int len2=a[i].size();
        //补len1-len2个0
        for(int j=1;j<=len1-len2;j++) a[i].push_back(0);
    }

    //接下来把a每一行倒着存进s
    //这样就可以实现高位在前 低位在后
    for(int i=1;i<=n;i++){
        string s;
        //倒着遍历，实现 高位在前，低位在后 的正确插入顺序
        for(int j=len1-1;j>=0;j--)
            s+=(a[i][j]+'0');
    
        //接下来再把s插入字典树
        insert(s);
    }
    
    //所有数字二进制插入完成后
    //开始遍历每一个数字 然后与字典树进行异或
    //如果1有通路就进入1，否则进入0 计算最大值
    for(int i=1;i<=n;i++){
        int ans=0;//存储本轮选中数字与字典树异或的最大值
        int p=0;//每一轮从字典树根节点开始
        string s;
        for(int j=len1-1;j>=0;j--){
            s+=(a[i][j]+'0');
        }
        //从最高位往最低位遍历
        for(int j=0;j<len1;j++){
        //当s[j]==1时 去看对应位数的字典树是否存在通往0路径
            if(s[j]=='1'){
                //如果0存在 就加上这一位的值
                if(tree[p].nxt[0]!=0){
                    ans+=pow(2,len1-j-1);
                    //然后移动指针位置
                    p=tree[p].nxt[0];
                }
                //否则就值不变 移动位置
                else  p=tree[p].nxt[1];
            }
         //当s[j]==0时 去看对应位数的字典树是否存在通往1路径
            else if(s[j]=='0'){
                if(tree[p].nxt[1]!=0){
                    ans+=pow(2,len1-j-1);
                    //然后移动指针位置
                    p=tree[p].nxt[1];
                }
                //否则就值不变 移动位置
                else  p=tree[p].nxt[0];
            }
        }
        sum=max(ans,sum);
    }
    cout<<sum;
    return 0;
}

版本二：位运算写法（竞赛标程）

//前面写法其实常数开销非常大 同时存在pow函数可能的精度问题
//是容易被卡掉的
//下面展示一个精简的位运算写法 运行速度是版本一的数十倍
#include <iostream>
#include <algorithm>//对应max函数
using namespace std;
int n;
int a[100010];//原数组，直接存十进制整数即可

struct treenode{
    int nxt[2];
}tree[4000010];

int pc;//记录当前开辟到了第几个节点
int sum;//异或得到的结果的最大值

//字典树异或查询
int query(int x){
    int ans=0;//记录x能在字典树内异或得到的最大异或结果
    int p=0;
    for(int i=30;i>=0;i--){
        //(x>>i)&1是位运算 通过将x右移i位并按位与1
        //能够快速精准地提取出x的第i位是0还是1
        int y=(x>>i)&1;

        //y^1也是位运算 0变1 1变0
        //z就是我们当前这一步希望走进去的相反通道
        int z=y^1;

        //如果渴望的相反分支被开辟过（存在）
        if(tree[p].nxt[z]!=0){
            ans+=(1<<i);//异或成功 加上这一位的权重
            p=tree[p].nxt[z];//走进相反分支
        }
        //如果相反分支是死路 只能走进与自己相同的分支
        //异或结果为0 不加分
        else p=tree[p].nxt[y];
        
    }
    //走到树底 返回这次异或最大值
    return ans;
}

//字典树插入
void insert(int x){
    int p=0;
    //统一从30位向下剥离 确保所有数字都在树上拥有相同长度的路径
    for(int i=30;i>=0;i--){
        int y=(x>>i)&1;//提取当前位
        //路径不存在 开辟新节点
        if(tree[p].nxt[y]==0) tree[p].nxt[y]=++pc;
        //下移
        p=tree[p].nxt[y];
    }
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n;
    //将每个整数插入字典树
    for(int i=1;i<=n;i++){
        cin>>a[i];
        insert(a[i]);
    }
    //遍历每个数字，与字典树进行异或找最大值
    for(int i=1;i<=n;i++){
        sum=max(sum,query(a[i]));
    }
    cout<<sum;
    return 0;
}