跳转至

异或运算专题 (XOR Properties & Classic Problems)

异或运算（Bitwise XOR，符号通常记为 \(\oplus\) 或代码中的 ^）是计算机二进制世界中最神奇、最优雅的位运算之一。

在算法竞赛与大厂技术面试中，异或因其无进位加法、自反性、结合律与偶数次消除等优良数学性质，衍生出了海量构思精巧的高频面试题（如寻找唯一数、前缀异或哈希、0-1 字典树最大异或对、Nim 博弈等）。

1. 异或的核心数学性质

异或运算的本质是：二进制位相同为 0，不同为 1（即模 2 加法，\(\text{bit}_1 \oplus \text{bit}_2 = (\text{bit}_1 + \text{bit}_2) \pmod 2\)）。

0 ^ 0 = 0
0 ^ 1 = 1
1 ^ 0 = 1
1 ^ 1 = 0

1.1 基础五大定律

  1. 归零律：任何数与自身异或结果为 0：\(x \oplus x = 0\)
  2. 恒等律：任何数与 0 异或保持不变：\(x \oplus 0 = x\)
  3. 交换律与结合律：参与异或的数的顺序不影响最终结果： \(a \oplus b = b \oplus a, \quad (a \oplus b) \oplus c = a \oplus (b \oplus c)\)
  4. 自反性（可逆性 / 异或逆元）： \(a \oplus b = c \iff a \oplus c = b \iff b \oplus c = a\)
  5. 直观理解：异或自己的逆元就是它自己。将同一个数异或两次等于什么都没做。
  6. 不进位加法：
  7. 两个数的二进制加法可以表示为：\(a + b = (a \oplus b) + ((a \ \& \ b) \ll 1)\)。
  8. 其中 \(a \oplus b\) 是不进位加法，\((a \ \& \ b) \ll 1\) 是进位部分。

2. 异或四大核心解题模型

graph TD
    A[异或核心解题模型] --> B["模型 1: 偶消奇存 (Single Number 家族)"]
    A --> C["模型 2: 前缀异或和 (Prefix XOR)"]
    A --> D["模型 3: 0-1 字典树 (0-1 Trie 最大异或)"]
    A --> E["模型 4: 状态压缩奇偶性 (Parity Bitmask)"]

    B --> B1["全部异或消除成对元素<br>lowbit 分组提取两个独立数"]
    C --> C1["XOR(L, R) = prefix[R] ^ prefix[L-1]<br>结合哈希表实现 O(n) 子数组检索"]
    D --> D1["高位到低位贪心走相反位<br>O(31) 极速求最大异或值"]
    E --> E1["二进制位 0/1 表示频次奇偶性<br>元音匹配 / 回文子串"]

3. 模型一：偶消奇存与 Single Number 家族

3.1 经典热身：只出现一次的数字 (LeetCode 136)

题目描述：给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。 要求：线性时间复杂度 \(O(n)\)，且仅使用 \(O(1)\) 额外空间。

解题思路：

利用交换律、结合律与归零律： 设出现两次的数分别为 \(a, b, c \dots\)，出现一次的数为 \(x\)。 将数组所有元素全部异或：

\[ (a \oplus a) \oplus (b \oplus b) \oplus \dots \oplus x = 0 \oplus 0 \oplus \dots \oplus x = x \]

所有成对出现的元素自身异或全部抵消为 0，最后剩下的正是单发元素 \(x\)！

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int result = 0;
        for (int x : nums) {
            result ^= x;
        }
        return result;
    }
};

3.2 进阶突破：只出现一次的两个数字 (LeetCode 260)

题目描述：给定一个整数数组 nums，其中恰好有两个元素只出现一次，其余所有元素均出现两次。找出只出现一次的那两个元素。 要求：\(O(n)\) 时间复杂度，\(O(1)\) 额外空间复杂度。

解题思路：

设这两个只出现一次的数为 \(x\) 和 \(y\)（\(x \ne y\)）。 1. 若对整个数组执行异或，最终得到的结果是 \(\text{xor\_all} = x \oplus y\)； 2. 因为 \(x \ne y\)，所以 \(\text{xor\_all} \ne 0\)。其二进制表示中必定至少有某一位是 1； 3. 二进制位为 1 意味着什么？说明 \(x\) 和 \(y\) 在这一位上的二进制值必定不同（一个是 0，另一个是 1）！ 4. 我们提取出 \(\text{xor\_all}\) 最低位的 1（即 lowbit = xor_all & (-xor_all)）； 5. 按该位是否为 1，将整个数组中的所有数字分为两组： - 组 1：该位为 1 的所有数（必定包含 \(x\) 和 \(y\) 中的某一个，以及成对出现的其他数）； - 组 2：该位为 0 的所有数（必定包含另一个，以及成对出现的其他数）； 6. 分别对这两组数据独立进行全量异或，成对的数各自在组内抵消，最终分别得到 \(x\) 和 \(y\)！

class Solution {
public:
    vector<int> singleNumber(vector<int>& nums) {
        long long xor_all = 0;
        for (int num : nums) {
            xor_all ^= num;
        }

        // 提取最低位的 1 (防止 INT_MIN 取反溢出，使用 long long)
        long long lowbit = xor_all & (-xor_all);

        int num1 = 0, num2 = 0;
        for (int num : nums) {
            if (num & lowbit) {
                num1 ^= num; // 该位为 1 的分组
            } else {
                num2 ^= num; // 该位为 0 的分组
            }
        }

        return {num1, num2};
    }
};

4. 模型二：前缀异或和 (Prefix XOR) 与子数组查询

4.1 核心性质

类似于前缀和数组（Prefix Sum），我们定义前缀异或数组 prefix：

\[ \text{prefix}[i] = a_1 \oplus a_2 \oplus \dots \oplus a_i \]

那么任意子数组 \([L, R]\) 的异或和可以通过两端的前缀异或值在 \(O(1)\) 时间内求得：

\[ \text{XOR}(L, R) = a_L \oplus a_{L+1} \oplus \dots \oplus a_R = \text{prefix}[R] \oplus \text{prefix}[L - 1] \]

证明： \(\text{prefix}[R] \oplus \text{prefix}[L - 1] = (a_1 \oplus \dots \oplus a_R) \oplus (a_1 \oplus \dots \oplus a_{L-1})\)。 前 \(L-1\) 项因为异或两次全部自我抵消为 0，正好剩下 \([L, R]\) 区间内的元素！

4.2 经典实战：每个元音包含偶数次的最长子字符串 (LeetCode 1371)

题目描述：给你一个字符串 s，请你返回满足以下条件的最长子字符串的长度：每个元音字母（'a', 'e', 'i', 'o', 'u'）在该子字符串中都恰好出现了偶数次。

解题思路（状态压缩 + 前缀异或）：

  1. 传统计数需要记录 5 个元音各自的出现次数，但题目只关心每个元音出现次数的“奇偶性”；
  2. 5 个元音的奇偶状态可以用一个 5 位的二进制掩码（Bitmask）表示：
  3. 范围从 00000 到 11111（共 32 种状态）；
  4. 第 0 位对应 'a'，第 1 位对应 'e'... 0 表示偶数次，1 表示奇数次；
  5. 每当遇到一个元音字母，我们翻转对应的位（例如遇到 'a'，状态执行 state ^= (1 << 0)）；
  6. 区间奇偶性转换：
  7. 子串 \([L, R]\) 中所有元音出现偶数次 \(\iff\) prefix_state[R] == prefix_state[L-1]；
  8. 两处状态完全相同时，异或差值为 0，说明这段区间内每个元音的变化次数都是偶数！
  9. 使用一个哈希表或长度为 32 的数组记录每个状态首次出现的下标，贪心拉大区间距离求最大长度。
#include <string>
#include <vector>
#include <algorithm>

class Solution {
public:
    int findTheLongestSubstring(std::string s) {
        // 存储 32 种状态首次出现的索引位置，初始化为 -2 表示尚未出现
        std::vector<int> first_pos(32, -2);
        first_pos[0] = -1; // 初始状态 00000 出现在下标 -1 处

        int state = 0;
        int max_len = 0;

        for (int i = 0; i < (int)s.length(); ++i) {
            char c = s[i];
            if (c == 'a') state ^= (1 << 0);
            else if (c == 'e') state ^= (1 << 1);
            else if (c == 'i') state ^= (1 << 2);
            else if (c == 'o') state ^= (1 << 3);
            else if (c == 'u') state ^= (1 << 4);

            if (first_pos[state] >= -1) {
                // 该状态之前出现过，计算当前区间长度
                max_len = std::max(max_len, i - first_pos[state]);
            } else {
                // 首次出现该状态，记录下标
                first_pos[state] = i;
            }
        }

        return max_len;
    }
};

5. 模型三：0-1 字典树 (0-1 Trie) 与最大异或对

5.1 核心问题：数组中两个数的最大异或值 (LeetCode 421)

题目描述：给你一个整数数组 nums，返回 nums[i] XOR nums[j] 的最大运算结果，其中 \(0 \le i \le j < n\)。 数据范围：\(n \le 2 \times 10^5\)，\(0 \le nums[i] \le 2^{31} - 1\)。 要求：\(O(n^2)\) 暴力枚举会超时，需在 \(O(n \log C)\) 时间内完成。

graph TD
    Root((Root))
    Root -->|bit 0| N0((0))
    Root -->|bit 1| N1((1))
    N0 -->|bit 0| N00((0))
    N0 -->|bit 1| N01((1))

    Note["0-1 Trie 贪心策略:<br>若当前数字在第 k 位是 1, 贪心优先走向 0 的分支 (使得异或结果该位为 1);<br>若对应分支不存在, 被迫走同向分支 (该位异或结果为 0)."]

贪心策略与 0-1 Trie 原理：

  1. 将每个 32 位整数的高位补 0 对齐为 31 位二进制串（从最高位第 30 位到第 0 位）；
  2. 构建一棵只包含 0 和 1 两个分支的二叉前缀树（0-1 Trie）；
  3. 针对每个数 \(x\) 寻找使其异或最大的配对数：
  4. 从最高位向最低位遍历 \(x\) 的每一位 \(b\)；
  5. 贪心选择：想要异或结果最大，当前位最好能异或出 1！因此优先检查 Trie 中是否存在相反位 \(1 - b\) 的分支；
  6. 若存在 \(1 - b\) 分支：顺着该分支走，当前位贡献值为 \(1 \ll k\)；
  7. 若不存在：只能被迫走同向位 \(b\) 的分支，当前位贡献值为 0；
  8. 单次查询只需走 31 步即可得出该数的全局最优解，总时间复杂度为 \(O(31 \times n) \approx O(n)\)！
#include <vector>
#include <algorithm>

struct TrieNode {
    TrieNode* child[2]{nullptr, nullptr};
};

class Solution {
private:
    TrieNode* root = new TrieNode();

    void insert(int num) {
        TrieNode* curr = root;
        for (int i = 30; i >= 0; --i) {
            int bit = (num >> i) & 1;
            if (!curr->child[bit]) {
                curr->child[bit] = new TrieNode();
            }
            curr = curr->child[bit];
        }
    }

    int queryMaxXOR(int num) {
        TrieNode* curr = root;
        int max_xor = 0;
        for (int i = 30; i >= 0; --i) {
            int bit = (num >> i) & 1;
            int opposite = 1 - bit;
            if (curr->child[opposite]) {
                max_xor |= (1 << i); // 成功走入相反位分支，该位为 1
                curr = curr->child[opposite];
            } else {
                curr = curr->child[bit];      // 被迫走同向分支，该位为 0
            }
        }
        return max_xor;
    }

public:
    int findMaximumXOR(std::vector<int>& nums) {
        for (int num : nums) {
            insert(num);
        }
        int ans = 0;
        for (int num : nums) {
            ans = std::max(ans, queryMaxXOR(num));
        }
        return ans;
    }
};

6. 模型四：博弈论与 Nim 和 (Nim-Sum)

在组合博弈论中，最经典的 Nim 游戏 的胜负完全由异或和决定： - 有 \(n\) 堆石子，石子数分别为 \(a_1, a_2, \dots, a_n\)； - 两人轮流取石子，每次只能从某一堆中取出任意数量的石子（至少取 1 颗），取走最后一颗石子的人获胜。

定理结论：

  • 定义 Nim 和 为所有堆石子数的异或和：
\[ S = a_1 \oplus a_2 \oplus \dots \oplus a_n \]
  • 若 \(S = 0\)：先手必败（P-position，必败态）；
  • 若 \(S \ne 0\)：先手必胜（N-position，必胜态）。先手总能找到某种合法的拿取方法，使得石子被拿取后的新状态异或和变为 0。

7. 异或常用技巧速查与避坑指南

7.1 无需临时变量交换两个数（面试经典陷阱）

void swap(int& a, int& b) {
    a ^= b;
    b ^= a;
    a ^= b;
}

[!CAUTION] 致命陷阱：如果 a 和 b 指向同一个内存地址（即 &a == &b，例如在数组原位排序中 swap(arr[i], arr[i])）： 第一步 a ^= b 会直接将该内存清零（a ^= a 变为 0），导致后续两步彻底将数据抹去变成 0！ 工业界强烈推荐使用 std::swap(a, b)，不仅不会出现上述 Bug，且编译器对其指令优化更为激进。

7.2 快速位运算公式表

  • 提取二进制最低位的 1（lowbit）：x & (-x)
  • 清除二进制最低位的 1：x & (x - 1)
  • 判断是否为 2 的幂次方：x > 0 && (x & (x - 1)) == 0
  • 获取二进制所有位翻转（全 1 掩码异或）：x ^ ((1 << n) - 1)