---
title: 最大的异或
date: 2022-05-04 11:39:20
permalink: /pages/b9402f/
---
## 📃 题目描述
题目链接：
- [剑指 Offer II 067. 最大的异或 - 力扣（LeetCode） (leetcode-cn.com)](https://leetcode-cn.com/problems/ms70jA/)
- [421. 数组中两个数的最大异或值 - 力扣（LeetCode） (leetcode-cn.com)](https://leetcode-cn.com/problems/maximum-xor-of-two-numbers-in-an-array/)
## 🔔 解题思路
整数的异或有一个特点，如果两个相同数位异或的结果是0，那么两个相反的数位异或的结果为 1。
**如果想找到某个整数 k 和其他整数的最大异或值，那么尽量找和 k 的数位不同的整数**。
因此，这个问题可以转化为查找的问题，而且还是按照整数的二进制数位进行查找的问题。需要将整数的每个数位都保存下来。前缀树可以实现这种思路，前缀树的每个节点对应整数的一个数位，路径对应一个整数。
由于每个节点只有两个分别表示 0 和 1 的子节点，因此前缀树节点的数据结构可以定义为如下所示的形式：
由于整数都是32位，它们在前缀树中对应的路径的
