位运算 · XOR 入门

1. 核心原理

位运算（bitwise operation） 指直接在整数的二进制表示上按位进行的逻辑运算，常见有 AND（&）、OR（|）、XOR（^）、NOT（~）和左移右移（<< / >>）。它把"对整数集合的操作"转换成"对一个机器字内若干位的并行操作"，单次代价是 O(1)，空间仅 O(1)。在面试题里出现的位运算可归纳为两类用途：一是把"有/无"、"奇/偶"、"是否选中"这类二值状态压进一个整数（每一位对应一个元素），二是直接利用 XOR 自反、n & (n-1) 抹最低位 1、n & -n 取 lowbit 等代数性质做线性扫描。

本节聚焦"按位操作的代数性质"，把单独看似零散的 idiom（取/设/清/翻第 k 位、popcount、lowbit、XOR 套路）归纳成一组可直接套用的模板。

1.1 朴素做法的局限

「按数组本身做扫描」是大多数题目的第一反应：例如统计一个整数二进制中 1 的个数，朴素写法是 while n: n //= 2; cnt += (n & 1)，每一步只处理一位，循环次数等于字长。再如"找出现一次的数"，第一反应是哈希表计数。这些写法功能上正确，但代价是 O(n) 空间或 O(字长) 时间，在工程上常被位运算 idiom 直接压成 O(1) 空间、循环次数等于 1 的个数（而非字长）。

1.2 关键洞察

把整数 x 看作长度固定的 0/1 序列后，三类操作可以做到 O(1)：

• 按位 mask 读写：用 1 << k 当作"只在第 k 位为 1"的探针，可单独取/设/清/翻任意一位。
• 整体代数性质：XOR 满足交换、结合、自反（a ^ a = 0）、零元（a ^ 0 = a），让一组数的 XOR 等于"出现奇数次的元素的 XOR"。
• lowbit 与抹 1：x & -x 取最低位 1 对应的 2 的幂；x & (x - 1) 抹掉最低位 1。两者循环次数等于 1 的个数。

剩余工作是把题面里的"集合 / 计数 / 奇偶"映射到这些 idiom 上。

1.3 模板要素

位运算题的统一骨架由两部分组成：

1. 基本 idiom（取/设/清/翻第 k 位、popcount、lowbit、XOR 全体）。这是工具集，§2 给出 mask 形式的完整模板。
2. 按位枚举的处理框架（外层 for k in range(BITS)，内层对所有元素取第 k 位再合并）。当问题不能用整体性质一次解决时，把每一位独立处理后再按位拼回——LC 137 / LC 1310 / 01-Trie 都是这一框架的应用。

1.4 套路类型一览

后面的 §3 / §4 会按"模板 A → B → C"的顺序，把 LC 136 / 137 / 260 串成一条 follow-up 链展开。

1.5 XOR 三大性质与"奇次数"推论

把 §1.2 提到的代数性质形式化为三条公理：

对任意整数序列 x₁, …, xₙ，由 P1 可任意重排把相同元素聚拢；由 P2，每凑齐两个相同的 vᵢ 即抵消为 0；由 P3，0 项不影响结果。所以：

任意一组数的 XOR，等价于"只把出现奇数次的元素再 XOR 一遍"的结果。

LC 136 一行解决，正是因为只有答案出现奇数次（1 次），其它都出现偶数次（2 次），整组 XOR 直接等于答案。LC 260 是相同结构（两个出现 1 次的元素，其它各出现 2 次）。而 LC 137 的难点在于"其它元素出现 3 次（仍是奇数次），P2 不会让它们抵消"——这正是 §4.2 中"按位 mod k"框架要解决的。

把 XOR 看成带"记忆"的累加器，初始值为 0，每读一个数就更新，扫到末尾即得答案：

整个过程 acc 只占一个机器字（LeetCode 上是 32 位整数），所以空间是 O(1)。

2. 通用模板

下面给出位运算的最小工具集：六个常用 idiom 的 mask 写法，加上一个"按位枚举处理"的统一骨架。骨架以 BITS = 32 为例（Python 任意精度，Java / C++ 的 int 本身就是 32 位补码），用来处理"无法整体一次性解决、需要逐位独立处理"的题。

BITS = 32                              # 32 位有符号整数

# === 六个基本 idiom ===
def get_bit(x: int, k: int) -> int:    # 读第 k 位（结果 0 或 1）
    return (x >> k) & 1

def set_bit(x: int, k: int) -> int:    # 把第 k 位置 1
    return x | (1 << k)

def clear_bit(x: int, k: int) -> int:  # 把第 k 位清 0
    return x & ~(1 << k)

def flip_bit(x: int, k: int) -> int:   # 翻转第 k 位
    return x ^ (1 << k)

def lowbit(x: int) -> int:             # 取最低位 1 对应的 2 的幂
    return x & -x

def popcount(x: int) -> int:           # 数 1 的个数
    cnt = 0
    while x:
        x &= x - 1                     # 抹掉最低位 1
        cnt += 1
    return cnt

# === 按位枚举处理（统一骨架）===
# 对每一位独立处理后按位拼回；适用于"整体性质不够、需要拆位"的题
def bitwise_scan(nums: list[int]) -> int:
    ans = 0
    for k in range(BITS):
        col = [(x >> k) & 1 for x in nums]   # 取第 k 列
        bit = process(col, k)                # 这一位的答案（题目相关）
        if bit:
            ans |= 1 << k
    # 处理 Python 负数：32 位补码意义下的高位 1 表示负数
    if ans >= 1 << (BITS - 1):
        ans -= 1 << BITS
    return ans

class BitTemplate {
    static final int BITS = 32;            // Java int 本身就是 32 位补码

    // === 六个基本 idiom ===
    static int getBit(int x, int k)   { return (x >> k) & 1; }
    static int setBit(int x, int k)   { return x | (1 << k); }
    static int clearBit(int x, int k) { return x & ~(1 << k); }
    static int flipBit(int x, int k)  { return x ^ (1 << k); }
    static int lowbit(int x)          { return x & -x; }       // 取最低位 1 对应的 2 的幂

    static int popcount(int x) {
        int cnt = 0;
        while (x != 0) {
            x &= x - 1;                    // 抹掉最低位 1
            cnt++;
        }
        return cnt;
        // 或一行：return Integer.bitCount(x);
    }

    // === 按位枚举处理（统一骨架）===
    static int bitwiseScan(int[] nums) {
        int ans = 0;
        for (int k = 0; k < BITS; k++) {
            int bitSum = 0;
            for (int x : nums) bitSum += (x >> k) & 1;   // 第 k 列的 1 计数
            int bit = process(bitSum, k);                 // 这一位的答案（题目相关）
            if (bit != 0) ans |= 1 << k;
        }
        return ans;                        // int 是补码，符号自动正确
    }
}

constexpr int BITS = 32;                   // C++ int 通常是 32 位补码

// === 六个基本 idiom ===
inline int  get_bit (int x, int k) { return (x >> k) & 1; }
inline int  set_bit (int x, int k) { return x | (1 << k); }
inline int  clear_bit(int x, int k){ return x & ~(1 << k); }
inline int  flip_bit(int x, int k) { return x ^ (1 << k); }
inline int  lowbit  (int x)        { return x & -x; }       // 取最低位 1 对应的 2 的幂

inline int popcount(int x) {
    int cnt = 0;
    while (x) {
        x &= x - 1;                        // 抹掉最低位 1
        cnt++;
    }
    return cnt;
    // 或一行：return __builtin_popcount(x);
}

// === 按位枚举处理（统一骨架）===
int bitwise_scan(const vector<int>& nums) {
    int ans = 0;
    for (int k = 0; k < BITS; k++) {
        int bit_sum = 0;
        for (int x : nums) bit_sum += (x >> k) & 1;        // 第 k 列的 1 计数
        int bit = process(bit_sum, k);                      // 这一位的答案（题目相关）
        if (bit) ans |= 1 << k;
    }
    return ans;                            // int 是补码，符号自动正确
}

四点需要注意：

• 运算符优先级：>> 比 & 紧、== 比 & 紧。mask >> i & 1 等于 (mask >> i) & 1、x & 1 == 1 在 C++/Java 里等于 x & (1 == 1)——判断时写括号：(x & 1) == 1。
• 1 << k 的类型：Java / C++ 里 1 << 31 是 Integer.MIN_VALUE、1 << 32 因"shift 长度取低 5 位"退化成 1；k 接近字长时改用 1L << k。
• Python 负数：Python 整数是任意精度，没有"高位 1 表示负数"的天然语义。按位枚举时若答案可能为负，末尾要手动 if ans >= 1 << (BITS - 1): ans -= 1 << BITS 还原符号。
• lowbit 与 x & (x - 1)：x & -x 给出"最低位 1 那一位的 2 的幂"，x & (x - 1) 把"最低位 1"抹成 0。两者循环次数都等于 popcount(x) 而非字长。

3. 母题精讲

LeetCode 136. 只出现一次的数字

LC 136 只出现一次的数字：给一个非空整数数组 nums，其中除一个元素只出现一次外，其它每个元素都恰好出现两次。返回那个只出现一次的元素。要求线性时间，并且不使用额外空间。

输入:  nums = [2, 2, 1]
输出:  1

输入:  nums = [4, 1, 2, 1, 2]
输出:  4

数据范围：1 ≤ len(nums) ≤ 3 × 10⁴，-3 × 10⁴ ≤ nums[i] ≤ 3 × 10⁴，保证只有一个元素出现一次、其余均出现两次。

3.1 第一反应：哈希表计数

任何"找出现次数特殊的元素"题，最朴素的解法都是哈希表：

from collections import Counter

class Solution:
    def singleNumber(self, nums: list[int]) -> int:
        cnt = Counter(nums)
        for x, c in cnt.items():
            if c == 1:
                return x

时间 O(n)，空间 O(n)——Counter 内部维护了 n / 2 + 1 个键值对。

这份代码功能上没错，但题面明确写着"不使用额外空间"。O(n) 空间在 n = 3 × 10⁴ 时勉强能跑，但在面试白板上写出来直接被追问："如果 n = 10⁹ 呢？哈希表内存放不下，怎么办？"——这就是空间约束的意义。

3.2 用集合优化一下：还是 O(n) 空间

另一种写法是用 set 做"出现过就移除"：

class Solution:
    def singleNumber(self, nums: list[int]) -> int:
        seen = set()
        for x in nums:
            if x in seen:
                seen.remove(x)
            else:
                seen.add(x)
        return next(iter(seen))

代码短了，但空间还是 O(n)（中途 set 大小可以涨到 n / 2）。它和 Counter 是同一个数量级，没有质变。

3.3 关键观察：成对的数能"互相抵消"

题面有一个很强的结构：除了答案，其它每个数都成对出现。我们想要的运算应该满足：

• 任意一个数和自己运算，结果是某个"零元"
• 任意一个数和"零元"运算，结果还是它自己
• 运算和顺序无关（这样我们可以一边扫一边累加，不用先排序、不用配对）

满足这三条的运算正好就是按位异或（XOR，记作 ⊕ 或 ^）。

把整个数组从左到右异或一遍，所有成对的数自己抵消成 0，剩下来的就是答案：

[4, 1, 2, 1, 2]
  4 ⊕ 1 ⊕ 2 ⊕ 1 ⊕ 2
= 4 ⊕ (1 ⊕ 1) ⊕ (2 ⊕ 2)   # 重新分组
= 4 ⊕ 0 ⊕ 0
= 4

代码只有一行核心：

from functools import reduce
from operator import xor

class Solution:
    def singleNumber(self, nums: list[int]) -> int:
        return reduce(xor, nums)

时间 O(n)，空间 O(1)——只用了一个累加变量。这才是题面想要的解。

下面把 LC 136 / 137 / 260 三道题在 §4 中链着讲清楚——从"出现 2 次"推广到"出现 3 次"，再到"两个答案"。

4. 三道例题：LC 136 → 137 → 260

下面按"原题 → follow-up → follow-up"链着讲。每道题都会显式回答："如果出题人把约束改成 XX，原解还能用吗？不能的话需要换什么工具？"

4.1 LC 136 只出现一次的数字（回头看）

回到 §3 的题目：

给一个非空整数数组 nums，其中除一个元素只出现一次外，其它每个元素都恰好出现两次。返回那个只出现一次的元素。

数据范围：1 ≤ len(nums) ≤ 3 × 10⁴，-3 × 10⁴ ≤ nums[i] ≤ 3 × 10⁴。

要求：线性时间，常数额外空间。

示例：

输入:  nums = [4, 1, 2, 1, 2]
输出:  4
解释:  4 出现 1 次，1 和 2 各出现 2 次。

解法：直接套模板 A。所有出现 2 次的元素由 P2 抵消成 0，再由 P3 与答案 XOR 后等于答案本身。

from functools import reduce
from operator import xor

class Solution:
    def singleNumber(self, nums: list[int]) -> int:
        return reduce(xor, nums)

• 时间 O(n)：单次线性扫描
• 空间 O(1)：只用 reduce 内部的一个累加变量

Follow-up（引出 LC 137）：现在出题人把约束改成"其它每个元素出现 3 次，仍然只有一个元素出现 1 次"——上面这行代码会怎么错？

观察 P2：a ⊕ a = 0，但 a ⊕ a ⊕ a = a（三个 a 抵消两个，剩一个）。如果对全体数组 XOR：

答案 + (出现 3 次的元素 v₁, v₂, …)
→ ans ⊕ v₁ ⊕ v₁ ⊕ v₁ ⊕ v₂ ⊕ v₂ ⊕ v₂ ⊕ …
= ans ⊕ v₁ ⊕ v₂ ⊕ …      # 每组三个抵消成一个

结果会把所有出现 3 次的元素也混进答案里。模板 A 在"成 k 次出现"且 k ≠ 2 时直接失效——这就是 LC 137 真正的难点。

4.2 LC 137 只出现一次的数字 II

LC 137：给一个非空整数数组，其中除一个元素只出现一次外，其它每个元素都恰好出现 3 次。找出那个只出现一次的元素。要求线性时间、常数空间。

数据范围：1 ≤ len(nums) ≤ 3 × 10⁴，-2³¹ ≤ nums[i] ≤ 2³¹ − 1。注意 nums[i] 现在可以是 32 位有符号整数的全范围，包括负数。

示例：

输入:  nums = [2, 2, 3, 2]
输出:  3

输入:  nums = [0, 1, 0, 1, 0, 1, 99]
输出:  99

思路：从"整体 XOR"换成"按位 mod 3"

XOR 本质上就是"按位的加法 mod 2"。LC 136 之所以能整体 XOR，是因为"其它元素出现 2 次" → 每一位的 1 计数都是 2 的倍数 → mod 2 后变 0。

把这一观察推广：

把 nums 里所有数按位竖着排列（每个数 32 行）。对第 i 列的 1 计数求和，再 mod k，就剩下答案在第 i 位的贡献。

LC 137 的 k = 3。具体来看：

i:           ... 6  5  4  3  2  1  0
nums[0]=2:        0  0  0  0  0  1  0
nums[1]=2:        0  0  0  0  0  1  0
nums[2]=3:        0  0  0  0  0  1  1   ← 答案
nums[3]=2:        0  0  0  0  0  1  0
            ----------------------------
列和:             0  0  0  0  0  4  1
mod 3:            0  0  0  0  0  1  1   = 3 ✓

每个出现 3 次的数对每一列贡献 0 或 3 个 1，mod 3 后清零；只有答案在它"为 1"的那些位上各留下一个 1。

代码

class Solution:
    def singleNumber(self, nums: list[int]) -> int:
        ans = 0
        for i in range(32):
            # 第 i 位上有多少个 1
            bit_sum = sum((x >> i) & 1 for x in nums)
            if bit_sum % 3:
                ans |= 1 << i
        # Python 整数没有"32 位上限"，需要手动还原符号
        if ans >= 1 << 31:
            ans -= 1 << 32
        return ans

逐段拆解：

• 外层循环 for i in range(32)：题面里 nums[i] 是 32 位有符号整数，所以最多检查 32 位。
• (x >> i) & 1：取 x 的第 i 位。Python 里 >> 对负数做的是"算术右移"——-1 右移 31 位仍然是 -1，而不是补码意义下的 1。但 & 1 会把它截到只剩最低位，结果仍然正确（详见 §5.1）。
• bit_sum % 3：如果是答案为 1 的位，列和会是 1 + 3m，mod 3 = 1；否则是 3m，mod 3 = 0。
• if ans >= 1 << 31: ans -= 1 << 32：把 32 位无符号结果手动还原成 Python 的有符号整数（详见 §5.2）。

复杂度：

• 时间 O(32 · n) = O(n)：32 是常数
• 空间 O(1)：只用了 ans 和循环变量

进阶（选读）：状态机解法 ones / twos

按位 mod 3 的写法清晰但常数偏大。如果想"一次扫完，不重读 32 遍"，可以用两个 32 位整数维护"每一位出现了 1 / 2 次的状态"：

class Solution:
    def singleNumber(self, nums: list[int]) -> int:
        ones = twos = 0
        for x in nums:
            ones = (ones ^ x) & ~twos
            twos = (twos ^ x) & ~ones
        return ones if ones < (1 << 31) else ones - (1 << 32)

数学上等价于"每一位独立维护一个三状态自动机：00 → 01 → 10 → 00"。第一次推荐先掌握按位 mod 3，状态机版可以作为面试时的进阶 follow-up。

Follow-up（引出 LC 260）：把约束再换一下——"其它元素出现 2 次，但有两个元素各出现 1 次"。模板 A 还能用吗？

整体 XOR 后会得到 a ⊕ b，没法直接拆出 a 和 b。但 a ⊕ b 至少能告诉我们一件事：它不等于 0（因为 a ≠ b），所以至少有一位上 a 和 b 不同。下一题的关键就在这"不同的某一位"上。

4.3 LC 260 只出现一次的数字 III

LC 260：给一个非空整数数组，其中恰好有两个元素只出现一次，其它每个元素都出现两次。找出这两个元素。返回顺序不限。要求线性时间、常数空间。

数据范围：2 ≤ len(nums) ≤ 3 × 10⁴，-2³¹ ≤ nums[i] ≤ 2³¹ − 1，保证恰好两个元素出现 1 次。

示例：

输入:  nums = [1, 2, 1, 3, 2, 5]
输出:  [3, 5]   或   [5, 3]

输入:  nums = [-1, 0]
输出:  [-1, 0]

思路：用"不同的一位"把数组切两半

设两个答案是 a 和 b。先对全体 XOR：

acc = a ⊕ b ⊕ (其它出现 2 次的元素全部抵消) = a ⊕ b

a ≠ b 意味着 acc ≠ 0，即 acc 里至少有一位是 1。这一位上 a 和 b 必然不同（一个是 0、另一个是 1）。

取出 acc 最低位的那个 1（记作 lowbit），按这一位是 0 还是 1 把整个数组切成两组：

• 第一组：在 lowbit 那一位为 1 的元素，必然包含 a、b 之一（不妨设是 a），且其它出现 2 次的元素也成对地全在这一组里（因为它们要么"这一位都是 0"要么"这一位都是 1"，作为一对不可能拆开）
• 第二组：在 lowbit 那一位为 0 的元素，包含另一个答案 b，以及剩下成对的元素

两组分别 XOR，由模板 A 就各自得到 a 和 b。

lowbit 是什么？

x & -x 是位运算里非常常见的小技巧，返回 x 最低位 1 所对应的那个 2 的幂。例如：

x       = 0b 0110 1100   (= 108)
-x      = 0b 1001 0100   (二进制补码下的相反数)
x & -x  = 0b 0000 0100   (= 4，刚好是最低位的那个 1)

为什么 x & -x 能取最低位？因为补码下 -x = ~x + 1：从最低位的 1 起往低位看，~x 全是 1、加 1 后只有那一位是 1，更低位都是 0；从最低位的 1 往高位看，~x 是 x 的"按位反转"，加 1 不会再传播，所以 x 和 -x 高位刚好互补。它们 AND 起来只有"最低位的 1"那一位是 1。

（详细证明放在 §5.3。）

代码

class Solution:
    def singleNumber(self, nums: list[int]) -> list[int]:
        xor_all = 0
        for x in nums:
            xor_all ^= x                  # = a ⊕ b

        lowbit = xor_all & -xor_all       # 取 a ⊕ b 最低位的 1

        a = b = 0
        for x in nums:
            if x & lowbit:                # 第一组：这一位为 1
                a ^= x
            else:                         # 第二组：这一位为 0
                b ^= x
        return [a, b]

逐段拆解：

• 第一遍扫描：算出 xor_all = a ⊕ b。a ≠ b 保证它不为 0。
• lowbit = xor_all & -xor_all：把"a 和 b 不同的那一位"单独拿出来。任何一位都行，取最低的只是写法上最方便。
• 第二遍扫描：按 lowbit 那一位把数组分两组。每组内部都满足"只有一个数出现 1 次，其它都出现 2 次"（成对元素绝不会跨组），用模板 A 各 XOR 一遍就得到答案。
• 返回 [a, b]：题面允许任意顺序。

复杂度：

• 时间 O(n)：两次线性扫描
• 空间 O(1)：只用了几个累加变量

到这里，"奇/偶次数"的核心套路就走完了一遍：

   出现 2 次 → 出现 3 次          → 出现 2 次但有两个答案
       ↓             ↓                       ↓
    模板 A      模板 B (按位 mod 3)      模板 C (lowbit 分组)
   reduce(xor)

接下来是把三道题里的"坑"集中拆解一下。

5. 边界、易错点、复杂度

5.1 Python 的负数右移：算术右移 vs 补码语义

Python 的 >> 对负数做的是算术右移，并且整数是任意精度——-1 不管右移多少位都还是 -1，因为它在 Python 里是"无穷多位 1"。

>>> -1 >> 31
-1
>>> -1 & ((1 << 32) - 1)
4294967295   # 把它截到 32 位无符号才是熟悉的 0xFFFFFFFF

在 §4.2 的代码里我们用 (x >> i) & 1：

• 即使 x 是负数，x >> i 仍然是负数（高位用 1 补），但**& 1 只保留最低位**，结果和"把 x 看成 32 位补码"是一致的。
• 所以位数遍历器（取第 i 位）的写法是安全的。

但累加 ans 时就有坑：

ans |= 1 << 31    # Python 里这是 +2147483648，而不是 -2147483648

如果题面的答案是负数（比如 -1，32 位补码全是 1），按位计数后 ans 会变成 2³² − 1（4294967295）。所以代码末尾必须手动还原符号：

if ans >= 1 << 31:
    ans -= 1 << 32

Java 和 C++ 的 32 位整数本身就是补码语义，没有这个还原步骤——LC 137 用 Java / C++ 实现时直接省掉 if ans >= ... 即可。

5.2 Java int 是 32 位补码：不需要还原但要小心溢出

Java 的 int 是 32 位有符号补码：

• 1 << 31 在 Java 里是 Integer.MIN_VALUE（-2³¹）
• (x >> i) & 1 直接得到补码意义下的第 i 位
• 整段代码不需要 if ans >= ... 的还原步骤

但要注意：1 << 31 在 Java 里是合法的（结果是 Integer.MIN_VALUE），1 << 32 会触发"shift 长度只取低 5 位"的语义，结果是 1 << 0 = 1，不是 0！如果想要 2³²，必须用 long：1L << 32。LC 137 / 260 因为 i 严格 < 32，不会踩这个坑，但写其它位运算题时要警觉。

5.3 lowbit 为什么是 x & -x：一行补码推导

设 x 的二进制是 ... b₃ b₂ b₁ 1 0 0 ... 0，其中最低位的 1 在第 k 位。

-x 在补码下等价于 ~x + 1：

x      = ... b₃ b₂ b₁ 1 0 0 ... 0
~x     = ... b̄₃ b̄₂ b̄₁ 0 1 1 ... 1
~x + 1 = ... b̄₃ b̄₂ b̄₁ 1 0 0 ... 0   (低 k 位的 1 全部进位归零，再在第 k 位置 1)

逐位与上 x：

• 比 k 低的位：x 是 0，结果是 0
• 第 k 位：x 是 1，-x 也是 1，结果是 1
• 比 k 高的位：bᵢ 和 b̄ᵢ 互补，AND 结果是 0

所以 x & -x = 1 << k，正好是最低位 1 的"那个 2 的幂"。

特殊情况：x = 0 时 -x = 0，x & -x = 0。所以在 LC 260 里我们隐含地用了"a ≠ b 保证 xor_all ≠ 0"这个前提。如果失去这个前提，需要单独处理。

5.4 三道题的复杂度对照

三道题的空间都是 O(1)，这就是 XOR 流派题目的标志——它们的对手永远是哈希表的 O(n) 空间。

6. 大厂真题作业

7. 这套工具下一步会在哪里出现

这一节学到的几个原子操作——XOR / n & -n lowbit / n & (n-1) / 按位枚举——在后续专题里都有"重型应用"。提前剧透一下：

下一节我们从"XOR 性质"走到"按位拆位（试填法）"，处理像 LC 421 最大异或对这一类需要在位上构造答案的题。再后面进入树状数组和状压 DP 时，这一节的原子操作会以"工具"身份反复出现。

8. 小结

XOR 入门只有一句话要记："一组数的 XOR = 出现奇数次的元素的 XOR"。LC 136 直接是这句话的字面应用；LC 137 把"奇/偶"换成"按位 mod 3"；LC 260 借 lowbit 把两个答案拆成两次独立的 LC 136。