一、 异或的基本性质（基石）

记住这四条，其他大多可以推导：

  1. 归零律：a ⊕ a = 0
  2. 恒等律：a ⊕ 0 = a
  3. 自反性（交换律与结合律的推论）：a ⊕ b ⊕ a = b
  4. 交换律与结合律：运算顺序和分组不影响结果。这使得前缀异或成为可能。

二、 前缀异或：子数组问题的利器

这是处理子数组异或和查询最核心的技巧，类似于前缀和。

  • 定义：设 pre[i] = a[1] ⊕ a[2] ⊕ ... ⊕ a[i]，并约定 pre[0] = 0。
  • 核心公式：a[l] ⊕ a[l+1] ⊕ ... ⊕ a[r] = pre[r] ⊕ pre[l-1]
    • 原理：pre[r] ⊕ pre[l-1] = (前缀到r) ⊕ (前缀到l-1)，根据结合律和归零律，相同的部分（前l-1项）抵消，剩下就是区间 [l, r] 的异或和。
  • 应用场景：
    • 快速求任意子数组异或和。
    • 将“子数组异或和为0”的条件转化为 pre[r] == pre[l-1]。这是解题的关键一步！
    • 问题转化为对前缀异或数组 pre 的分析，常结合哈希表（unordered_map）来统计次数、寻找配对。

三、 位运算的独特性质（解题突破口）

  1. 不进位加法/减法：异或在每一位上独立操作。a ⊕ b 在二进制下，每一位的规则是“相同为0，不同为1”。这暗示我们可以按位考虑问题。
  2. 判断奇偶性（结合律的妙用）：
    • 多个数异或，结果的最低位 等于 所有数最低位的异或。
    • 而一个数二进制最低位为 1 代表奇数，为 0 代表偶数。
    • 推论：在一堆数中，异或结果的奇偶性 等于 所有数奇偶性的异或。这在一些博弈或奇偶分类问题中有用。
  3. 与加法的关系：a ⊕ b <= a + b。等号成立当且仅当 a 和 b 的二进制表示没有同时为1的位（即 a & b == 0）。这个性质在涉及“最大异或和”与“和”的比较时常用。
  4. 构造互补对：对于任意数 x，存在唯一的数 y，使得 x ⊕ y = (全1的二进制串)，这个 y 等于 ~x（在限定位数下）。在构造题中，常用 (1<<k)-1 - x 来得到与 x 在 k 位下每一位都相反的数。

    四、 经典题型与技巧

  5. 寻找唯一出现奇数次的数：利用 a⊕a=0，将所有数异或，出现偶数次的会两两抵消，结果就是那个出现奇数次的数。
  6. 寻找两个只出现一次的数（其他出现两次）：
    • 第一步：将所有数异或，得到 x = a ⊕ b（a, b 为所求）。
    • 第二步：找到 x 的任意一个为 1 的二进制位。这一位意味着 a 和 b 在这一位上不同。
    • 第三步：根据这一位将原数组分成两组，分别异或，得到的两个结果就是 a 和 b。
  7. 最大/最小异或对问题：
    • 暴力：O(n^2) 对于大数据不行。
    • 优化（O(n*logC)）：使用01-Trie（字典树）。将数字按二进制从高位到低位插入Trie，查询时尽量“走相反位”可以得到最大异或值，“走相同位”可以得到最小异或值。这是必须掌握的高级数据结构。
  8. 异或相关的构造题（如你刚才遇到的）：
    • 核心目标：控制前缀异或数组 pre 的值。
    • 常用手段：
      • 让 pre 数组的值是 0 到 n 的一个排列，然后微调（例如交换两个值）来满足特定区间异或为0的条件。
      • 利用性质：如果 pre[l-1] = pre[r]，则区间 [l, r] 异或为0。要保证其他区间不为0，就要保证其他任意 pre[i] 与 pre[j] 都不相等（除了我们特意制造的那一对相等）。
      • 注意题目对 a[i] 取值范围的限制（如 1 <= a[i] <= 1e9），这要求 pre[i] ⊕ pre[i-1] 的结果必须在这个范围内。通常用连续整数构造 pre 可以满足。

五、 做题时的注意事项（避坑指南）

  1. 注意数据范围和溢出：你刚才遇到的问题就是典型。当使用2的幂构造时，2^30 ≈ 1e9，所以区间长度不能超过30。必须时刻检查构造值是否在允许范围内。
  2. 小心 0：异或中 0 是单位元，非常特殊。在构造时，如果允许元素为 0，可能会意外产生多个异或为0的子数组（例如单个元素为0）。题目常要求正整数来避免这种情况。
  3. 前缀异或的初始化：务必定义 pre[0] = 0，这样才能正确表示从 a[1] 开始的子数组。
  4. 调试方法：对于小数据，可以暴力计算所有子数组的异或和来验证你的构造是否正确。

  5. 思维转化：遇到“所有子数组异或和不为0”这类强条件，要立刻想到它等价于“前缀异或数组 pre 中所有元素两两不同（且 pre[0]=0 也不与其他重复）”。这大大简化了问题。

    六、 推荐的巩固练习方向

  6. 基础：LeetCode 136（只出现一次的数字）、LeetCode 268（缺失数字）。

  7. 进阶：LeetCode 260（只出现一次的数字 III）、LeetCode 421（数组中两个数的最大异或值）（必做，练习01-Trie）。
  8. 综合与构造：Codeforces 上的许多构造题（难度 1500-1800），比如你刚才做的这道题的原型。多观察题解中是如何利用前缀异或性质进行构造的。

总结一下，异或问题的核心思路是：利用前缀异或转化区间问题，利用归零律和结合律进行抵消与配对，利用位独立性进行按位处理或使用Trie。多练习，你会对这种“魔力”运算越来越有感觉。

因为异或可以逆运算，所以此处直接先算1-n的异或和再和现在的异或和异或一下就行了。
这样就找到了那个没有出现过的数字。
找出现奇数次的数字时，可以直接异或，因为只有一个数字满足这个要求，那么最后剩下的那个就是无法完成匹配的数字，就是答案了。
找两个只出现一次的数字时，也是先异或得到$x=x_1\oplus x_2$，然后看不一样的那一位来分开数组。
解释：就是看这一位是否是1，然后就和只出现一次的数那题一样了。出现两次的数，分组一定在一起，那么就相互异或抵消了。