异或运算符算法题应用总结

目录

• 性质
• 一、高频应用场景
• • **场景1：寻找唯一不重复的元素**
  • **场景2：寻找两个不重复的元素**
  • **场景3：不用加减号做算术运算**
  • **场景4：状态切换与奇偶判断**
  • **场景5：交换两个变量**
• 二、综合训练题单（按难度排序）
• 三、高频误区提醒
• 四、面试高频追问

---

性质

异或运算（^）在算法题中有四大核心性质，掌握后可以快速解决多类问题：

核心性质

1. 自反性：a ^ a = 0（相同数异或为0）
2. 恒等性：a ^ 0 = a（与0异或不变）
3. 交换律：a ^ b = b ^ a
4. 结合律：(a ^ b) ^ c = a ^ (b ^ c)

---

一、高频应用场景

场景1：寻找唯一不重复的元素

适用条件：数组中只有一个元素出现奇数次，其余都出现偶数次
原理：所有元素异或后，成对的自动抵消为0，最终剩下目标值

入门题目：

• LeetCode 136. 只出现一次的数字- 最经典入门题
• LeetCode 268. 丢失的数字- 索引和值的巧妙对应
• LeetCode 1486. 数组异或操作- 直接模拟异或过程

场景2：寻找两个不重复的元素

适用条件：数组中有两个元素只出现一次，其余都出现两次
思路：先全体异或得到x = a ^ b，找到x中任意为1的位（表示a,b在该位不同），按此位将数组分为两组分别异或

进阶题目：

• LeetCode 260. 只出现一次的数字 III- 分组建异或技巧
• 剑指 Offer II 070. 只出现一次的数字- 同上题

场景3：不用加减号做算术运算

原理：利用异或实现无进位加法，与运算实现进位
典型应用：

• LeetCode 371. 两整数之和- 用位运算实现加法
• LeetCode 面试题 17.01. 不用加号的加法- 同上

场景4：状态切换与奇偶判断

小技巧：

• x ^= 1可在0和1之间切换（等价于!x）
• x ^ 1可判断奇偶（比%2更快）

场景5：交换两个变量

经典三行代码，无需临时变量：

a^=b;b^=a;a^=b;

---

二、综合训练题单（按难度排序）

序号	题目	难度	核心考点	链接
1	只出现一次的数字	★☆☆☆☆	基础异或	LeetCode 136
2	丢失的数字	★☆☆☆☆	索引异或	LeetCode 268
3	数组异或操作	★☆☆☆☆	模拟异或	LeetCode 1486
4	两整数之和	★★☆☆☆	位运算加法	LeetCode 371
5	只出现一次的数字 III	★★★☆☆	分组异或	LeetCode 260
6	使数组异或和为零	★★★☆☆	动态规划+异或	LeetCode 1787
7	黑板异或游戏	★★★★☆	博弈论+异或	LeetCode 810
8	子数组异或查询	★★☆☆☆	前缀异或	LeetCode 1310

---

三、高频误区提醒

• ❌ 初始值设为1（必须为0）
• ❌ 用加法替代异或（无法消除成对元素）
• ❌ 忽略"出现偶数次"的前提条件

---

四、面试高频追问

1. 如果只出现一次的数字有两个，怎么办？→ 参考LeetCode 260的分组策略
2. 如果其他数字出现三次呢？→ 需要结合位计数或状态机（如LeetCode 137）
3. 异或和哈希表哪个更好？→ 异或空间O(1)更优，但哈希表更通用
4. 证明异或满足交换律？ → 可从真值表或二进制位角度说明

建议从LeetCode 136开始，配合题解区的高赞分析，逐步建立位运算思维！