位运算
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 / 常见坑
把 XOR 和 OR 搞混。
XOR(
⊕,^)是"不同位"。OR(|)是"任一位为 1"。 在符号丛里看起来很像,但在"每个元素两次除了一个"这类问题里干的完全相反的事 —— OR 给你的是所有元素的按位或,没有意义。忘了 XOR 的单位元是 0。
累加器初始化为
0,而不是 arr[0]。0 ⊕ x = x, 所以从 0 开始让循环体能统一处理每一个元素。从 arr[0] 开始也行, 但当问题推广时,那个差一就成了 bug 的发源地。逻辑 AND 与按位 AND 不分。
多数语言里
&& 短路,返回布尔;& 才是按位运算。 混用会悄悄改变表达式的类型,破坏算式。Python 里 and 是逻辑,& 是按位 —— 在像布尔的值附近要格外小心。05 / 去 LeetCode 上练习
简单19
01Add Binary— LC 67→02Single Number— LC 136→03Reverse Bits— LC 190→04Number of 1 Bits— LC 191→05Power of Two— LC 231→06Missing Number— LC 268→07Power of Three— LC 326→08Counting Bits— LC 338→09Power of Four— LC 342→10Find the Difference— LC 389→11Convert a Number to Hexadecimal— LC 405→12Fizz Buzz— LC 412→13Hamming Distance— LC 461→14Number Complement— LC 476→15Complement of Base 10 Integer— LC 1009→16Number of Steps to Reduce a Number to Zero— LC 1342→17Sort Integers by The Number of 1 Bits— LC 1356→18XOR Operation in an Array— LC 1486→19Check if the Sentence Is Pangram— LC 1832→
中等20
01Reverse Integer— LC 7→02Divide Two Integers— LC 29→03Pow(x, n)— LC 50→04Subsets— LC 78→05Single Number II— LC 137→06Repeated DNA Sequences— LC 187→07Bitwise AND of Numbers Range— LC 201→08Single Number III— LC 260→09Maximum Product of Word Lengths— LC 318→10Sum of Two Integers— LC 371→11Maximum XOR of Two Numbers in an Array— LC 421→12Total Hamming Distance— LC 477→13Beautiful Arrangement— LC 526→14Partition to K Equal Sum Subsets— LC 698→15Maximum Length of a Concatenated String with Unique Characters— LC 1239→16Number of Steps to Reduce a Number in Binary Representation to One— LC 1404→17Decode XORed Permutation— LC 1734→18Minimum Number of Work Sessions to Finish the Tasks— LC 1986→19Fair Distribution of Cookies— LC 2305→20Bitwise XOR of All Pairings— LC 2425→
困难7
01Shortest Path Visiting All Nodes— LC 847→02Find the Shortest Superstring— LC 943→03Smallest Sufficient Team— LC 1125→04Parallel Courses II— LC 1494→05Maximum Number of Achievable Transfer Requests— LC 1601→06Minimum One Bit Operations to Make Integers Zero— LC 1611→07Distribute Repeating Integers— LC 1655→