位运算
01 / 一句话本质
把整数当作它的二进制位看,而不是它的数值。 一个数和自己 异或(XOR) 得 0,和 0 异或保持不变。 这套模式的难点在于看出问题里隐藏的位级结构。
题目找出唯一不重复的元素输入[2, 3, 5, 4, 5, 3, 4]
arr
2
3
5
4
5
3
4
acc
0
0
0
0
0
0
0
0
= 0
7 个整数的数组。每个数都出现两次,只有一个例外。用 XOR 折叠整个数组找出它。
步
0 / 15
累加器
0
当前
—
结果
—
0 / 15
02 / 模式骨架
# XOR 折叠 —— 找出只出现一次的元素result ← 0for x in arr:result ← result ⊕ xreturn result# XOR 满足交换律 + 结合律, 且 a ⊕ a = 0:# 每一对重复元素都互相抵消,留下来的就是唯一的那个。# 同样的骨架适用于:popcount、bitmask DP、按位枚举子集。
03 / 什么时候用这个模式
"出现一次 / 两次 / k 次"
重复与唯一性是 XOR 的招牌。每个元素出现两次,除了一个 是 XOR-fold 的经典原型;每个元素出现三次,除了一个 则转化为按位取模。
"子集 / 幂集"
N 个元素的每个子集都对应一个 N 位的位掩码。 让 mask 从 0 跑到 2^N − 1 就能枚举出每个子集恰好一次 —— 当 N ≤ 20 时,比递归更快、更紧凑。"统计 1 的个数 / 奇偶性"
popcount(
x & (x − 1) 清除最低位的 1)和奇偶性是两根支柱。 它们出现在汉明距离、平衡字符串、格雷码等问题里。"不用额外变量交换 / O(1) 额外空间"
一道明显该用哈希集的题被限制成 O(1) 额外空间 是最响亮的提示。 这个约束几乎总在那里是因为 XOR 能把答案压在一个整数里。
04 / 常见坑
i.
把 XOR 和 OR 搞混。
XOR(
⊕,^)是"不同位"。OR(|)是"任一位为 1"。 在符号丛里看起来很像,但在"每个元素两次除了一个"这类问题里干的完全相反的事 —— OR 给你的是所有元素的按位或,没有意义。ii.
忘了 XOR 的单位元是 0。
累加器初始化为
0,而不是 arr[0]。0 ⊕ x = x, 所以从 0 开始让循环体能统一处理每一个元素。从 arr[0] 开始也行, 但当问题推广时,那个差一就成了 bug 的发源地。iii.
逻辑 AND 与按位 AND 不分。
多数语言里
&& 短路,返回布尔;& 才是按位运算。 混用会悄悄改变表达式的类型,破坏算式。Python 里 and 是逻辑,& 是按位 —— 在像布尔的值附近要格外小心。05 / 去 LeetCode 上练习
四道题,按难度排序。这里有意不放解答。