数组中两个数的最大异或值如何求？（LeetCode 421）

简化版

最大异或值要让高位尽量为 1，因为高位贡献更大。常见解法是把所有数的二进制位插入 0/1 前缀树，然后对每个数从高位到低位贪心找相反位：当前位是 0 就优先找 1，当前位是 1 就优先找 0。每个数查一次，32 位整数下时间 O(32n)，空间 O(32n)。

详细版

class Node {
    Node[] child = new Node[2];
}

int findMaximumXOR(int[] nums) {
    Node root = new Node();
    for (int x : nums) {
        Node cur = root;
        for (int b = 31; b >= 0; b--) {
            int bit = (x >>> b) & 1;
            if (cur.child[bit] == null) cur.child[bit] = new Node();
            cur = cur.child[bit];
        }
    }

    int ans = 0;
    for (int x : nums) {
        Node cur = root;
        int val = 0;
        for (int b = 31; b >= 0; b--) {
            int bit = (x >>> b) & 1;
            int want = bit ^ 1;
            if (cur.child[want] != null) {
                val |= (1 << b);
                cur = cur.child[want];
            } else {
                cur = cur.child[bit];
            }
        }
        ans = Math.max(ans, val);
    }
    return ans;
}

异或某一位为 1 的条件是两个数该位不同。
为了最大化数值，必须优先保证更高位为 1。
0/1 前缀树能快速判断某个高位前缀下是否存在相反位。
固定 32 位整数下时间 O(n)，展开写为 O(32n)，空间 O(32n)。

完整版教学

一、为什么不能直接枚举所有数对

暴力会枚举所有 (i,j)，计算 nums[i] ^ nums[j] 并取最大值，时间 O(n^2)。当 n=20000 时，数对约 2 亿个，很容易超时。优化的切入点不是减少异或本身，而是避免盲目试所有搭档。

异或值的大小由高位优先决定。例如第 30 位为 1 的结果，一定大于第 30 位为 0、低位全为 1 的结果。因此寻找最大异或时要从高位开始贪心。

二、最大异或的贪心依据

某一位上，0 ^ 1 = 1，1 ^ 0 = 1，相同才是 0。对一个固定数字 x，如果当前位是 0，就希望另一个数字当前位是 1；如果当前位是 1，就希望另一个数字当前位是 0。

x 当前位 bit = 0 -> want = 1
x 当前位 bit = 1 -> want = 0
want = bit ^ 1

由于从高位到低位处理，只要更高位已经能变成 1，就不应该为了低位牺牲高位。这就是贪心正确的关键。

三、为什么需要 0/1 前缀树

如果每一位都想找相反位，必须知道数组中是否存在某个数拥有对应的二进制前缀。0/1 前缀树把每个数字按二进制从高位到低位插入，每条根到叶的路径代表一个数字。

nums = [3, 10, 5]
用 4 位表示：
3  = 0011
10 = 1010
5  = 0101

root
├─0
│ ├─0 -> 3 的前缀
│ └─1 -> 5 的前缀
└─1 -> 10 的前缀

查询某个 x 时，从根开始优先走相反位；如果相反位不存在，才走相同位。这样每一步都在当前可行集合里让当前位尽量为 1。

记忆钩子：最大 XOR 不是找“数值最大的另一个数”，而是从最高位开始找“和我最不一样的前缀”。

四、用具体例子走查询过程

设 nums=[3,10,5,25,2,8]，经典答案是 5 ^ 25 = 28。

5  = 00101
25 = 11001
XOR= 11100 = 28

对 5 查询时，高位开始尽量找相反位：

5 的位:      0 0 1 0 1
希望搭档位:  1 1 0 1 0
25 的位:     1 1 0 0 1
实际 XOR:    1 1 1 0 0

不是每一位都一定能找到相反位，但高位能找到时优先拿下。最终形成的 11100 已经比很多低位更优的组合更大。

五、前缀哈希的另一种写法

除了前缀树，也可以按位贪心加哈希集合。每轮假设当前高位答案可以变成 candidate = ans | (1 << bit)，把所有数的高位前缀放入集合，检查是否存在两个前缀异或出 candidate。

int ans = 0, mask = 0;
for (int b = 31; b >= 0; b--) {
    mask |= (1 << b);
    Set<Integer> prefixes = new HashSet<>();
    for (int x : nums) prefixes.add(x & mask);
    int candidate = ans | (1 << b);
    for (int p : prefixes) {
        if (prefixes.contains(p ^ candidate)) {
            ans = candidate;
            break;
        }
    }
}

这个写法空间也是 O(n)，思路更数学；前缀树写法更直观，适合讲“逐位找相反位”。

解法	核心判断	时间复杂度	适合场景
暴力枚举	直接算每个数对的 XOR	O(n^2)	只适合小数据或验证答案
0/1 前缀树	对每个数逐位找相反分支	O(32n)	讲解最直观，支持动态插入
哈希前缀	假设当前答案位可为 1，检查前缀是否存在	O(32n)	代码较短，适合熟悉异或等式时使用

六、复杂度和实现细节

前缀树插入每个数需要扫描 32 位，查询每个数也扫描 32 位，所以时间 O(64n)，简化为 O(n)。空间上最坏每个数字贡献 32 个节点，因此 O(32n)。

实现细节里最容易错的是位宽和右移。Java 中建议使用 >>> 取位，表达无符号位模式；如果输入都非负，>> 多数情况下也能工作，但 >>> 更稳。若题目限定数字小于 2^31，从 bit 30 开始也可以；从 31 开始更通用。

七、常见误区与追问

误区：选择数组中最大的两个数异或。 最大数值不等于最大异或，高位是否相反才关键。
误区：从低位开始贪心。 低位贡献小，不能为了低位 1 牺牲高位 1。
误区：前缀树查询时只看当前位，不维护路径可行性。 每一步都必须沿着真实存在的路径走，否则拼出的搭档可能不存在。
追问：为什么贪心是正确的？ 因为二进制数按高位决定大小，高位能置 1 时任何低位选择都无法弥补放弃高位的损失。
追问：前缀树和哈希前缀法哪个更好？ 前缀树直观且一次建树多次查询；哈希前缀法代码短，但正确性解释更抽象。
追问：如果是动态插入和查询怎么办？ 前缀树更合适，可以插入新数后立即查询最大异或搭档。

八、加强记忆

最大异或值的核心是“高位优先找相反”。把数字放进 0/1 前缀树，查询时当前位为 0 就优先走 1，当前位为 1 就优先走 0；走到相反位时把答案对应位设为 1。不要被“最大数字”误导，真正要最大化的是从最高位开始的差异前缀。

简化版

详细版