文昌市网站建设_网站建设公司_全栈开发者_seo优化

性质

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

核心性质

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（必须为0）
• ❌ 用加法替代异或（无法消除成对元素）
• ❌ 忽略"出现偶数次"的前提条件

四、面试高频追问

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

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