01字典树查异或最大值因高位优先贪心：从第31位起逐位选异或为1的分支，时间复杂度O(32n)远优于O(n²)暴力枚举，关键在固定32位无符号处理、插入后查询、显式初始化指针。
为什么用 01 字典树（Trie）查异或最大值
因为异或的性质是：相同为 0、不同为 1，所以想让 a ^ b 尽可能大，就要让高位尽可能多地为 1。暴力枚举所有数对是 O(n²)，而 01 字典树可以把每次查询压到 O(32)（32 位整数），总复杂度降到 O(n × 32)，实际非常快。
关键点不是“存数”，而是“按二进制位从高到低插入和查询”——高位优先决策，才能贪心保证结果最优。
怎么建 01 字典树（以 int 为例）
每个节点只有两个子指针：child[0] 和 child[1]，分别代表当前位是 0 或 1。插入时从第 31 位（符号位）开始，逐位右移取 bit：
struct TrieNode {
TrieNode* child[2] = {};
};
void insert(TrieNode* root, int x) {
TrieNode* p = root;
for (int i = 31; i >= 0; --i) {
int bit = (x >> i) & 1;
if (!p->child[bit]) p->child[bit] = new TrieNode();
p = p->child[bit];
}
}
- 必须固定位宽（如 32），否则负数右移行为不一致；
int直接用unsigned int或强制转成无符号再移位更安全 - 不需要存值或计数，除非你要支持删除或查频次
- 初始化
root = new TrieNode()，别忘了分配内存
怎么查与给定数异或的最大值
核心是贪心：对每一位，优先走能让该位异或结果为 1 的分支。比如当前位是 bit，那就尽量选 child[1 - bit]；如果不存在，只能走 child[bit]。
C++ Code Review Master
下载
组合式C++代码评审方案，融合静态分析、AI推理、多轮迭代评审和C++专项检查，适用于PR审查、增量代码审查、全项目评审和代码质量评分，触发词包括review cpp、cpp代码评审、C++review、代码审查。
立即学习“C++免费学习笔记（深入）”；
int queryMaxXor(TrieNode* root, int x) {
TrieNode* p = root;
int res = 0;
for (int i = 31; i >= 0; --i) {
int bit = (x >> i) & 1;
int want = 1 - bit;
if (p->child[want]) {
res |= (1 << i);
p = p->child[want];
} else {
p = p->child[bit];
}
}
return res;
}
- 注意
res是边走边构造结果，不是最后算x ^ found - 如果树里只有一个数，也能正确返回它与自身的异或（即 0），但通常你查的是“已插入的其他数”，所以插入顺序很重要：先插前面的数，再对当前数查最大异或
- 不能复用同一个
query结果去反推另一个操作数——这棵树只支持“查最大异或值”，不直接返回配对数字（如需，可加val字段在叶子记录原数）
常见错误和边界注意
最常踩的坑不是逻辑，而是位运算细节和内存管理：
-
(x >> i) & 1对负数在某些编译器下会补符号位，建议统一用unsigned int u = static_cast<unsigned int>(x)</unsigned>再移位 - 没初始化
child[2]数组为{}，导致野指针访问——务必显式初始化为nullptr - 查询前忘记插入任何数，
root下为空，第一次p->child[...]就崩溃 - 以为可以查“数组中任意两数的最大异或”，却把所有数一次性插入后对每个数都查——这样会包含自身（
a ^ a == 0），正确做法是边插边查：遍历数组，对nums[i]查询当前树中（即nums[0..i-1]）的最大异或，再插入nums[i]
真正卡住人的地方，往往在第 31 位处理和负数表示上——哪怕题目说“非负整数”，也建议统一走无符号路径，省去判断。
