💠 01-数据结构与算法 · 主题 12:位运算¶
位运算题量不大但一题一思路(异或去重、清除最低位、集合枚举),会了就是送分题。 本 notebook 目标:背熟 6 个 trick → 吃透 8 道高频题 → 通过 25 道自测。
前置:无强依赖。运行环境:Python 3.8+。
核心概念¶
(a) 🗂️ 位运算:六大 trick 与 8 道高频题¶
位运算题量不大但一题一思路:异或去重、清除最低位、集合枚举,会了就是送分题。本 notebook 背熟 6 个 trick,吃透 8 道高频题,并补状态压缩入门。
flowchart TB
N1["💠 位运算基础:6 个运算符"] --> N2["六大 trick:背熟"]
N2 --> N3["异或去重:136"]
N2 --> N4["数 1 个数 / 2 的幂 / 缺失数字"]
N4 --> N5["位运算 + DP:338"]
N2 --> N6["汉明距离 / 颠倒二进制:461 / 190"]
N6 --> N7["集合枚举与状态压缩"]
N7 --> N8["常见坑:补码与负数"]
N8 --> N9["面试追问与自测"]
- N1 · 位运算基础:直接在二进制位上操作:与 &、或 |、异或 ^、取反 ~、左右移 << >>。核心性质"异或两次等于还原"是整个章节的地基。
- N2 · 六大 trick:x^0=x、x^x=0、x&-x 取最低位 1、x&(x-1) 清除最低位 1、n&1 判奇偶、1<<k 造掩码——全部背下来,做题时直接调用。
- N3 · 异或去重 136:只出现一次的数字:全员异或,成对出现的数互相抵消,剩下的就是那个"唯一"——一题顶十题的经典。
- N4 · 数 1 个数等三题:普及 trick 组合:数 1 的个数用 x&(x-1) 循环清除;2 的幂只有一位是 1;缺失数字用"补位异或"配对找缺。
- N5 · 位运算 + DP 338:比特位计数把"去掉最低位 1 的数 + 1"写成递推:dp[i] = dp[i>>1] + (i&1),是位运算和 DP 的结合题。
- N6 · 汉明距离 / 颠倒二进制:汉明距离 = 两数异或后数 1 的个数;颠倒二进制位逐位取出再左移拼接,两题都练"按位搬运"。
- N7 · 集合枚举与状态压缩:位运算还能当"集合"用:整数每一位表示一个元素的取舍,子集枚举和状态压缩 DP 都靠它(第 k 位 = 1 表示选第 k 个元素)。
- N8 · 常见坑:Python 整数无限长、负数按补码存储、>> 对负数是算术右移(补 1)——位运算题必须想清楚符号位才不会翻车。
- N9 · 面试追问与自测:为什么负数用补码(统一加减)、a^=b;b^=a;a^=b 交换原理、位运算在工程(权限位/布隆过滤器)里的场景,配自测清单。
§1 位运算基础(背熟)¶
| 运算符 | 含义 | 例子 |
|---|---|---|
& |
按位与 | 5 & 3 = 1(101 & 011) |
\| |
按位或 | 5 \| 3 = 7 |
^ |
按位异或 | 5 ^ 3 = 6 |
~ |
取反 | ~5 = -6(补码) |
<< |
左移(×2) | 1 << 3 = 8 |
>> |
右移(÷2) | 8 >> 2 = 2 |
六大 trick(面试核心)¶
- 异或自反:$a \oplus a = 0$,$a \oplus 0 = a$ → 成对出现可抵消
- 清除最低位 1:
x & (x - 1)→ 把最右边的 1 变成 0(数 1 个数、判 2 的幂) - 取最低位 1:
x & (-x)→ 得到只含最低位 1 的数(树状数组、lowbit) - 判第 k 位:
(x >> k) & 1 - 置位/清位:
x | (1 << k)(置 1);x & ~(1 << k)(清 0) - 交换不用临时变量:
a ^= b; b ^= a; a ^= b(面试题梗,实际工程不用)
Python 注意¶
- 整数无限位宽,负数用补码(
-x = ~x + 1) x & (x-1)对负数同样适用(补码下有意义)- Python 有内置
bin(x).count('1'),但面试要求手写
§2 只出现一次的数字(LeetCode 136):异或¶
题目:非空数组,只有一个元素出现 1 次,其余恰好 2 次,找出它。
公式:全体异或:
$$(a_1 \oplus a_2 \oplus \cdots \oplus a_n) = \text{只出现一次的数}$$
因为每对相同数异或为 0,0 ⊕ x = x。
复杂度:$O(n)$ 时间,$O(1)$ 空间(对比哈希 $O(n)$ 空间)。
💡 变体一:137 每个数出现 3 次——用位计数模 3(
(sum(第k位1的个数) % 3) << k组装)。 💡 变体二:260 有两个唯一数——先全体异或得到a^b,取最低位 1 分组再分别异或。
✍️ §3.1 手算位运算两招:数 1 的个数 + 异或找单数¶
Brian Kernighan:
n &= n-1每次消掉最右边一个 1;异或:a ^ a = 0、a ^ 0 = a——13 与 [4,1,2,1,2] 手算。
第 1 招:13 有几个 1($13=1101_2$)
$$n=1101\xrightarrow{\&\ (n-1)=1100}1100\xrightarrow{\&\ 1011}1000\xrightarrow{\&\ 0111}0000$$
消了 3 次 → 3 个 1。
第 2 招:异或找单数([4,1,2,1,2] 里 4 只出现一次)
$$4\oplus1\oplus2\oplus1\oplus2=(4)\oplus(1\oplus1)\oplus(2\oplus2)=4\oplus0\oplus0=\mathbf{4}$$
手算收获:
n & (n-1)的奥妙:减 1 会把最右的 1 变成 0、其后所有 0 变 1,与运算恰好消掉那个 1——每次循环消一个 1,循环次数 = 1 的个数- 异或的交换结合律让"成对的都归零":单数自然剩下——$O(n)$ 时间、$O(1)$ 空间,比哈希省空间(§2 只出现一次)
- 位运算优先级坑:
&低于==,写(n & (n-1)) == 0判断 2 的幂(§7 常见 bug) - 面试延伸:位运算常用于状态压缩枚举子集(§6)、集合枚举,2 的幂/汉明距离都是一招鲜
下面 numpy 复算。
# ---- §3.1 验证:numpy 复算位运算 ----
x = 13
c, t = 0, x
while t:
t &= t - 1
c += 1
print(f'13 = {bin(13)} → {c} 个 1')
assert c == 3
nums = [4, 1, 2, 1, 2]
r = 0
for n in nums:
r ^= n
print(f'异或找单数 = {r}')
assert r == 4
print('\n✓ 与手算一致')
# ---- matplotlib 中文字体(防图内中文乱码)----
import matplotlib
matplotlib.rcParams['font.sans-serif'] = ['Microsoft YaHei', 'SimHei', 'Songti SC', 'Arial Unicode MS', 'DejaVu Sans']
matplotlib.rcParams['axes.unicode_minus'] = False
# -------------------------------------------
# ============== 136 / 260 只出现一次的数字(异或抵消 + 分组) ==============
# 【题目目标】① 136:数组中只有一个数出现 1 次、其余恰好出现 2 次,找出它;
# ② 260:有两个数只出现一次、其余出现 2 次,找出这两个数
# 【算法思路】异或性质 a^a=0、0^a=a:① 全体异或一遍,成对的数互相抵消,剩下
# 的就是唯一数;② 先全体异或得 x=a^b(a、b 不同故 x 非零),取 x 的
# 最低位 1(该位 a、b 必不同)作为分组依据,按此位把数组分成两组再
# 分别异或,组内成对抵消后各剩一个唯一数
# 【变量含义】nums:输入数组;res/x:异或累积结果;mask:x 的最低位 1
# (x & -x);a/b:两个分组各自的异或结果;v:遍历中的元素
# 【循环不变量】res = 已扫描部分成对抵消后的剩余异或值;260 两轮遍历结束后
# a、b 分别等于两个组内的唯一数
# 【递归终止】无递归;遍历完数组即结束
# 【关键边界】分组掩码必须取 x & -x(最低位 1),不能随便取其他非零位;分组
# 判断用 v & mask 是否非零;负数在补码下异或性质同样成立
# 【复杂度】两题均为 O(n) 时间、O(1) 空间
# 136. 只出现一次的数字:数组中只有一个数出现 1 次,其余都出现 2 次,用异或找出它
# 核心原理:a^a=0、0^a=a,全体异或一遍,成对的数互相抵消,剩下的就是唯一数
def single_number(nums):
res = 0 # 异或结果,从 0 开始(0 是异或幺元)
for x in nums: # 遍历数组中的每个数
res ^= x # 累计异或,出现两次的数会抵消
return res # 剩下的就是只出现一次的数字
# 260. 只出现一次的数字 III:有两个数只出现一次,其余都出现两次,找出这两个数
# 思路:整体异或得 x=a^b;取 x 的最低位 1(该位 a、b 必不同),按此位分组再异或
def single_numbers_260(nums):
# 第一步:全体异或,成对的抵消,剩下 x = a ^ b
x = 0 # 异或结果
for v in nums: # 第一次遍历,全体异或
x ^= v # x = a ^ b
mask = x & (-x) # 最低位 1:a、b 在这一位不同
a = b = 0
for v in nums:
if v & mask: # 按该位分组
a ^= v
else:
b ^= v
return [a, b]
print('136:', single_number([4, 1, 2, 1, 2])) # 期望 4
print('136:', single_number([2, 2, 1])) # 期望 1
print('260:', sorted(single_numbers_260([1, 2, 1, 3, 2, 5]))) # 期望 [3, 5]
136: 4 136: 1 260: [3, 5]
§3 位 1 的个数(191)/ 2 的幂(231)/ 缺失数字(268)¶
191 汉明重量(数 1 的个数)¶
trick:n = n & (n - 1) 每次消掉一个 1:
$$\text{popcount}(n) = \#\{ \text{循环} n \& (n-1) \text{直到} n = 0 \}$$
复杂度:$O(\text{位数中 1 的个数})$ ≤ $O(32/64)$。
231 2 的幂¶
$$n > 0 \ \land \ (n \& (n - 1)) = 0$$
因为 2 的幂二进制只有一个 1(1, 10, 100, 1000...)。
268 缺失数字¶
思路:[0..n] 全部异或上数组所有数,成对的抵消,剩下的就是缺失值:
$$(0 \oplus 1 \oplus \cdots \oplus n) \oplus (\text{nums 全体}) = \text{缺失值}$$
# ============== 191 位 1 个数 / 231 2 的幂 / 268 缺失数字 ==============
# 【题目目标】① 191:统计二进制数中 1 的个数(汉明重量);② 231:判断整数是否
# 为 2 的幂;③ 268:数组长度为 n、原序列应为 0..n,找出缺失的那个数
# 【算法思路】核心 trick:n & (n-1) 每执行一次就把最低位的 1 变成 0:191 循环
# 清除并计数,清除次数即 1 的个数;231 要求 n>0 且清除一次后变为 0
# (2 的幂只有一个 1);268 把 0..n 全部下标与数组全部值异或一遍,
# 配对的「下标 × 值」互相抵消,剩下的就是缺失值
# 【变量含义】n:输入整数 / 数组长度;cnt:1 的个数计数器;res:异或累积结果;
# i:遍历下标;x/nums:数组元素
# 【循环不变量】191:每轮清除一个最低位 1 且 cnt 同步 +1;268:每轮把下标 i 与
# 值 nums[i] 异或进 res
# 【递归终止】191 的 while n 循环到 n==0;268 两轮循环结束
# 【关键边界】191 必须用 while n(位宽不固定,不能写固定次数的 for);231 先判
# n>0(0 与负数不是 2 的幂);268 下标范围 0..n 共 n+1 个,恰好与
# 缺一个值的 0..n 序列配对
# 【复杂度】191:O(位数);231:O(1);268:O(n) 时间、O(1) 空间
# 191. 位 1 的个数(汉明重量):统计一个二进制数中 1 的个数
# 核心技巧:n & (n-1) 会把 n 最低位的 1 变成 0,能消几次就说明有几个 1
def hamming_weight(n):
cnt = 0 # 计数器:记录 1 的个数
while n: # 只要 n 还不为 0,说明还有 1 可以清除
n &= n - 1 # 清除最低位 1(把最右边的 1 变成 0)
cnt += 1 # 每清除一个 1,计数加 1
return cnt # 返回 1 的个数
# 231. 2 的幂:2 的幂的二进制表示中只有一个 1(如 1、10、100)
def is_power_of_two(n):
return n > 0 and (n & (n - 1)) == 0 # 正数,且清除最低位 1 后变成 0
# 268. 缺失数字:数组长度为 n,原序列应为 0..n,找出缺失的那个数
# 核心技巧:把 0..n 与数组所有数异或一遍,成对的抵消,剩下的就是缺失值
def missing_number(nums):
res = 0 # 异或累积结果,从 0 开始
n = len(nums) # 数组长度(完整序列应有 n+1 个数)
for i in range(n + 1): # 先异或完整的 0..n
res ^= i # 0..n 全异或
for x in nums: # 再异或数组中的每个数
res ^= x # 再异或数组
return res # 成对抵消后剩下的就是缺失的数字
print('191:', hamming_weight(11)) # 期望 3(1011)
print('191:', hamming_weight(0)) # 期望 0
print('231:', is_power_of_two(16), is_power_of_two(18), is_power_of_two(1), is_power_of_two(0))
print(' 期望 True False True False')
print('268:', missing_number([3, 0, 1])) # 期望 2
print('268:', missing_number([0, 1])) # 期望 2
print('268:', missing_number([9, 6, 4, 2, 3, 5, 7, 0, 1])) # 期望 8
191: 3
191: 0
231: True False True False
期望 True False True False
268: 2
268: 2
268: 8
§4 比特位计数(338):位运算 + DP 组合¶
题目:返回 0..n 每个数的二进制 1 个数。
DP 转移(核心):右移一位 + 最低位信息:
$$\text{popcount}(i) = \text{popcount}(i >> 1) + (i \& 1)$$
因为右移把最低位丢掉,i & 1 补回它。
复杂度:$O(n)$ 时间(比逐个 popcount $O(n \log n)$ 优),$O(1)$ 额外空间。
💡 另一个等价转移:
popcount(i) = popcount(i & (i-1)) + 1。
# ============== 338 比特位计数(位运算 + DP 递推) ==============
# 【题目目标】返回 0..n 每个数字二进制表示中 1 的个数组成的数组
# 【算法思路】DP 递推:popcount(i) = popcount(i >> 1) + (i & 1)——i 右移一位
# (去掉最低位)得到更小的数 i>>1,其 1 个数已算过,再加回最低位本身;
# 等价写法 popcount(i) = popcount(i & (i-1)) + 1(先清除最低位 1 再补 1)
# 【变量含义】n:上界;dp:结果数组,dp[i] 即 i 的 1 个数;i:当前数字
# 【循环不变量】dp[i] 只依赖下标更小的 dp[i>>1](或 dp[i&(i-1)]),均已先算好
# 【递归终止】无递归;for 循环从 1 到 n 结束
# 【关键边界】dp[0]=0(0 的 1 个数为 0);i 从 1 开始遍历(0 已在初始化中处理)
# 【复杂度】O(n) 时间、O(n) 空间(输出本身)
# 338. 比特位计数:返回 0..n 每个数字的二进制中 1 的个数
# DP 转移:popcount(i) = popcount(i >> 1) + (i & 1),即去掉最低位后补回最低位
def count_bits(n):
dp = [0] * (n + 1) # dp[i] 记录数字 i 中 1 的个数,dp[0] = 0
for i in range(1, n + 1): # 从 1 递推到 n
dp[i] = dp[i >> 1] + (i & 1) # 去掉最低位 + 补回最低位
return dp # 返回 0..n 的完整结果数组
# 另一种等价递推:popcount(i) = popcount(i & (i-1)) + 1(先清除一个 1 再补回 1)
def count_bits_v2(n):
dp = [0] * (n + 1)
for i in range(1, n + 1):
dp[i] = dp[i & (i - 1)] + 1 # 清除一个 1 再补 1
return dp
print('338:', count_bits(5)) # 期望 [0, 1, 1, 2, 1, 2]
print('338:', count_bits(0)) # 期望 [0]
print('v2 一致:', count_bits_v2(8) == count_bits(8))
338: [0, 1, 1, 2, 1, 2] 338: [0] v2 一致: True
# ============== 461 汉明距离 / 190 颠倒二进制位 ==============
# 【题目目标】① 461:两个整数二进制位不同的个数(汉明距离);② 190:把 32 位
# 无符号整数的二进制位逆序(低位变高位)
# 【算法思路】461:x^y 后不同位为 1,问题转为「数 1 的个数」,直接复用 191 的
# n&(n-1) 计数技巧;190:逐位搬运——结果 res 左移一位腾出最低位,用
# n&1 取出 n 的最低位放入,再 n 右移一位;固定重复 32 次
# 【变量含义】x/y:两个输入整数;xor:x^y;dist:计数;n:输入;res:颠倒结果
# 【循环不变量】461:每轮清除 xor 一个最低位 1、计数 +1;190:循环 i 次后 res 的
# 低 i 位恰为 n 原低 i 位的逆序
# 【递归终止】461 的 while xor 到 0;190 固定循环 32 次结束
# 【关键边界】190 必须固定 32 次——用 while n 会丢掉高位的 0;负数按 32 位补码
# 看待(符号位也参与颠倒)
# 【复杂度】461:O(位数);190:O(1)(固定 32 次);空间均 O(1)
# 461. 汉明距离:两个整数二进制的不同位数 = 异或结果中 1 的个数
def hamming_distance(x, y):
return hamming_weight(x ^ y) # 异或后不同位为 1,复用 191 的数 1 逻辑
# 190. 颠倒二进制位:把 32 位二进制数逆序(从最低位开始逐位搬到结果的最低位)
def reverse_bits(n):
res = 0 # 结果,初始为 0
for _ in range(32): # 固定处理 32 位(LeetCode 190 按 32 位无符号整数)
res = (res << 1) | (n & 1) # 结果左移腾出低位,把 n 的最低位放进去
n >>= 1 # n 右移一位,准备处理下一位
return res # 返回颠倒后的结果
print('461:', hamming_distance(1, 4)) # 期望 2(001 vs 100)
print('461:', hamming_distance(3, 1)) # 期望 1
print('190:', reverse_bits(43261596)) # 期望 964176192
print('190(0):', reverse_bits(0)) # 期望 0
print('190(全1):', reverse_bits(0xFFFFFFFF)) # 期望 0xFFFFFFFF
461: 2 461: 1 190: 964176192 190(0): 0 190(全1): 4294967295
§6 集合枚举与状态压缩(位运算扩展)¶
子集枚举¶
n 个元素的任意子集 ↔ 一个 n 位二进制数:第 i 位 1 = 选第 i 个元素:
$$\text{子集个数} = 2^n \ (\text{mask} = 0 \dots 2^n - 1)$$
for mask in range(1 << n):
subset = [nums[i] for i in range(n) if (mask >> i) & 1]
状态压缩 DP 入门¶
状态 = visited 集合(mask & (1 << i) 判是否访问过 i),经典:旅行商、划分为 k 个相等子集(698)。
复杂度提示:$2^n$ 个状态 × 每状态 $O(n)$ 转移 → $O(n \cdot 2^n)$,n ≤ 20 时可接受。
# ============== 78 子集(位枚举版,对照回溯版) ==============
# 【题目目标】用位运算枚举生成数组的全部子集(与主题 7 的回溯版结果一致)
# 【算法思路】n 位二进制数 mask 表示一个子集:第 i 位为 1 表示选 nums[i];枚举
# mask 从 0 到 (1<<n)-1,对每个 mask 遍历每一位收集元素
# 【变量含义】n:数组长度;res:结果列表;mask:子集掩码(0..2^n-1);sub:当前
# mask 对应的子集;i:位下标
# 【循环不变量】每个 mask 唯一对应一个子集,共 2^n 个,互不重复
# 【递归终止】无递归;mask 枚举完即结束
# 【关键边界】(mask>>i)&1 判断第 i 位是否为 1;空 mask=0 对应空集;n 较大时
# 2^n 会爆内存,仅适合小规模
# 【复杂度】O(n·2^n) 时间(每个 mask 检查 n 位)、O(2^n) 空间(输出)
# 78. 子集(位枚举法):用 n 位二进制数 mask 表示一个子集,第 i 位为 1 表示选 nums[i]
def subsets_by_bit(nums):
# 位枚举版子集(对照主题 7 的回溯版)
n = len(nums) # 数组长度
res = [] # 收集所有子集
for mask in range(1 << n): # 枚举 0 ~ 2^n-1,共 2^n 个子集
sub = [] # 当前 mask 对应的子集
for i in range(n): # 检查每个元素是否被选中
if (mask >> i) & 1: # 第 i 位为 1 → 选中 nums[i]
sub.append(nums[i]) # 加入当前子集
res.append(sub) # 收集这个子集
return res # 返回全部子集
s = subsets_by_bit([1, 2, 3])
print('位枚举子集个数:', len(s)) # 期望 8
print('按 mask 序:', s)
expected = [[], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3]]
print('与回溯版结果集一致:', sorted(map(tuple, s)) == sorted(map(tuple, expected))) # 期望 True
位枚举子集个数: 8 按 mask 序: [[], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3]] 与回溯版结果集一致: True
§7 常见 bug 与边界(面试踩坑区)¶
- 异或结果混淆:
a ^ b是「不同位为 1」,不是「相加/相减」;计数要用 popcount - 负数右移:Python
n >>= 1对负数做算术右移(补 1),数位个数的题先把负数转正或改用n & (n-1)法 x & -x在 Python:无限位宽下-x = ~x + 1,x & (-x)仍正确取最低位 1(正数场景)- 位宽假设:
1 << 31在 Python 无溢出(任意大),但 LeetCode 190 明确 32 位——循环固定 32 次 - 运算符优先级:
(mask >> i) & 1必须加括号,&优先级低于== ~x陷阱:取反结果带符号(~5 = -6),清位要写成x & ~(1 << k)而不是x & !(...)
§9 自测清单(L1 必会 / L2 进阶 / L3 挑战)¶
L1 必会(10 题)¶
- 1. 只出现一次的数字(LeetCode 136)
- 2. 位 1 的个数(191)
- 3. 2 的幂(231)
- 4. 缺失数字(268)
- 5. 汉明距离(461)
- 6. 四的幂(342)
- 7. 交替位二进制数(693)
- 8. 数字的补数(476)
- 9. 二进制求和(67)
- 10. 颠倒二进制位(190)
L2 进阶(10 题)¶
- 11. 只出现一次的数字 II(137)
- 12. 只出现一次的数字 III(260)
- 13. 比特位计数(338)
- 14. 两整数之和(371,位运算加法)
- 15. 子集(78,位枚举法)
- 16. 二进制中 1 的个数(剑指 Offer 15,面试常问)
- 17. UTF-8 编码验证(393)
- 18. 数字范围按位与(201)
- 19. 最大单词长度乘积(318,位掩码)
- 20. 转换为 16 进制数(405)
L3 挑战(5 题)¶
- 21. 位运算实现加减乘除(无乘除号做除法 29)
- 22. 划分为 k 个相等的子集(698,状压)
- 23. 最大的异或(421,字典树+位)
- 24. 戳气球(312 的状压视角)
- 25. 最短超级串(943,TSP 状压)
自测要点¶
- 3 分钟内盲写:136 + 191 + 231
- 讲清
x & (x-1)与x & -x的区别与用途 - 能手推 338 的 DP 转移公式
§10 高频补充:只出现一次的数字 II / 两整数之和 / 数字范围按位与 / 二进制求和¶
137 只出现一次的数字 II(其余元素各出现 3 次)¶
- 异或只能解决"出现 2 次"(奇偶抵消);出现 3 次时需逐位统计:
对所有数字的某一位统计 1 的个数,
cnt % 3即为唯一数在该位的值。 - 实现:循环 32 位,
cnt = sum((x >> i) & 1 for x in nums),cnt % 3 == 1则置位。 - Python 注意:整数任意精度、负数补码视为无限长,用
mask = (1 << 32) - 1截断到 32 位, 最后若符号位(第 31 位)为 1 则减2**32还原成负数。
# ============== 137 只出现一次的数字 II(位计数模 3) ==============
# 【题目目标】其余元素各出现 3 次,只有一个数出现 1 次,找出它(异或只解决
# 「出现 2 次」,出现 3 次要换思路)
# 【算法思路】逐位统计:对每个二进制位统计所有数在该位为 1 的次数,对 3 取模——
# 出现 3 次的元素在该位的 1 会被 3 整除抵消,余下的 1 就是唯一数在该位
# 的取值;把每一位的结果用 1<<i 组装回整数(本质是 3 进制不进位加法)
# 【变量含义】nums:数组;res:按位组装的结果;i:位下标;cnt:第 i 位上 1 的
# 个数(用 sum 生成器统计);x:数组中的每个数
# 【循环不变量】res 已确定的位与「只出现一次的数」对应位的值一致
# 【递归终止】无递归;固定遍历 32 个二进制位
# 【关键边界】取模是 % 3 而非 % 2(出现 3 次);Python 整数无限位宽,只需统计
# 32 位即可覆盖 int32 范围;结果若符号位为 1(res >= 1<<31),需减
# 1<<32 把补码还原成真正负数
# 【复杂度】O(32·n) ≈ O(n) 时间、O(1) 空间
# 137. 只出现一次的数字 II:其余元素各出现 3 次,只有一个数出现 1 次
# 思路:异或只能解决“出现 2 次”,出现 3 次时要逐位统计 1 的个数并对 3 取模
def single_number_ii(nums):
# 位计数模 3:对每一位统计 1 的出现次数 % 3,组装出唯一数
res = 0 # 结果,按位拼接
for i in range(32): # 按 32 位整数逐位处理
cnt = sum((x >> i) & 1 for x in nums) # 第 i 位上 1 的个数
if cnt % 3: # 出现 3 次的元素在此位会被 3 整除,余 1 说明唯一数该位为 1
res |= 1 << i # 把第 i 位置为 1
if res >= (1 << 31): # 符号位为 1 → 负数还原
res -= 1 << 32 # 从补码表示还原为真正的负数
return res # 返回只出现一次的数字
print('137:', single_number_ii([2, 2, 3, 2])) # 期望 3
print('137:', single_number_ii([0, 1, 0, 1, 0, 1, 99])) # 期望 99
print('137 负数:', single_number_ii([-2, -2, 1, -2])) # 期望 1
print('137 负数:', single_number_ii([1, 1, 1, -3])) # 期望 -3
137: 3 137: 99 137 负数: 1 137 负数: -3
# ============== 371 两整数之和(位运算加法) ==============
# 【题目目标】不使用 + 号,仅用位运算实现整数加法(支持负数与 32 位溢出回绕)
# 【算法思路】加法拆成两步迭代:a^b 得到无进位和,(a&b)<<1 得到进位;把进位
# b 迭代为 0 即完成;用 MASK=0xFFFFFFFF 模拟 32 位补码截断;最终结果
# 符号位为 1(a > 0x7FFFFFFF)时减 1<<32 还原为真正的负数
# 【变量含义】a/b:两个加数(b 在循环中演进位);carry:进位值;MASK:32 位掩码
# 【循环不变量】a 恒等于「已处理位数的无进位和」,b 恒等于尚未处理完的进位
# 【递归终止】while b 循环到进位为 0 停止
# 【关键边界】负数必须先 & MASK 截断成 32 位补码;a^b 与 carry 每步都要 & MASK
# 保持 32 位语义;返回前判 a<=0x7FFFFFFF,否则减 1<<32 还原负数;
# INT_MAX+1 会溢出回绕成 INT_MIN(测试验证了该行为)
# 【复杂度】O(位数) 时间、O(1) 空间
# 371. 两整数之和:不使用 + 号,只用位运算实现整数加法
def get_sum(a, b):
# 位运算加法:a ^ b = 无进位和,(a & b) << 1 = 进位;迭代到进位为 0
MASK = 0xFFFFFFFF # 32 位掩码,模拟补码截断
a &= MASK # 把 a 截断为 32 位补码
b &= MASK # 把 b 截断为 32 位补码
while b: # 还有进位就继续循环
carry = (a & b) << 1 # 进位:同为 1 的位左移一位
a = (a ^ b) & MASK # 无进位和:不同为 1 的位异或
b = carry & MASK # 下一轮处理进位
return a if a <= 0x7FFFFFFF else a - (1 << 32) # 符号还原:超出正数范围转负数
print('371:', get_sum(1, 2)) # 期望 3
print('371:', get_sum(-1, 2)) # 期望 1
print('371 溢出:', get_sum(2147483647, 1)) # 期望 -2147483648(32 位溢出回绕)
print('371 溢出:', get_sum(-2147483648, -1)) # 期望 2147483647
371: 3 371: 1 371 溢出: -2147483648 371 溢出: 2147483647
# ============== 201 数字范围按位与(公共前缀法) ==============
# 【题目目标】求 [m, n] 闭区间内所有整数按位与的结果
# 【算法思路】公共前缀法:区间内所有数按位与 = m、n 的「公共二进制前缀」后面
# 补 0(区间跨越某一位的翻转时,该位及其低位必为 0);实现:m、n 同时
# 右移直到相等(丢弃不一致的高位),记录移位次数 shift,再把公共前缀
# 左移回位、低位补 0
# 【变量含义】m/n:区间端点;shift:右移次数(即需要补回的低位 0 个数)
# 【循环不变量】每轮右移都在丢弃一个 m、n 不一致的高位,直到前缀一致
# 【递归终止】while m < n 循环到 m==n 时结束
# 【关键边界】m==n 时直接返回 m(无需移位);区间含 0 时结果必为 0(右移多次
# 后 m 变 0 且 shift 足够大)
# 【复杂度】O(位数) 时间、O(1) 空间
# 201. 数字范围按位与:求 [m, n] 闭区间内所有整数按位与的结果
# 思路:公共前缀法——按位与结果 = m、n 的公共二进制前缀后面补 0
def range_bitwise_and(m, n):
# 公共前缀法:[m, n] 区间按位与 = m、n 的公共二进制前缀补 0
# m、n 同时右移直到相等,记录移位次数,再把公共前缀左移回来
shift = 0 # 记录右移的次数
while m < n: # 未对齐说明还有不同的高位,继续右移
m >>= 1 # m 右移一位
n >>= 1 # n 右移一位
shift += 1 # 移位次数加 1
return m << shift # 把公共前缀左移回去,低位补 0
print('201:', range_bitwise_and(5, 7)) # 期望 4(101 & 110 & 111)
print('201:', range_bitwise_and(0, 0)) # 期望 0
print('201 大数:', range_bitwise_and(1, 2147483647)) # 期望 0
print('201:', range_bitwise_and(12, 15)) # 期望 12
201: 4 201: 0 201 大数: 0 201: 12
# ============== 67 二进制求和(模拟竖式加法) ==============
# 【题目目标】两个二进制字符串相加,返回二进制和字符串
# 【算法思路】手写竖式加法:从最低位(字符串末尾)开始,逐位求和并记录进位,
# 当前位 = 和的二进制最低位(s&1),进位 = 和右移一位(s>>1);处理完
# 剩余进位后把结果反转成高位到低位
# 【变量含义】a/b:两个二进制字符串;i/j:从右往左的指针;carry:进位(0/1);
# s:当前位三个输入(进位 + a 位 + b 位)之和;res:逆序存储的结果位
# 【循环不变量】处理完右起若干位后,res 前缀与 a、b 已处理低位之和一致
# 【递归终止】while i>=0 or j>=0 or carry:两串都处理完且进位为 0 时结束
# 【关键边界】指针越界的一侧按 0 参与求和;结束时若 carry 仍为 1 需补一位;
# 结果在最后统一反转(append 是 O(1),头插是 O(n))
# 【复杂度】O(max(len(a), len(b))) 时间与空间
# 67. 二进制求和:两个二进制字符串相加,返回和的二进制字符串
def add_binary(a, b):
# 手写二进制字符串相加:从低位到高位模拟进位,最后反转结果
i, j = len(a) - 1, len(b) - 1 # 两个指针指向两个字符串的最低位(末尾)
carry = 0 # 进位,初始为 0
res = [] # 按低位到高位顺序保存每一位结果
while i >= 0 or j >= 0 or carry: # 任一字符串没处理完或有进位就继续
s = carry # 当前位的和从进位开始
if i >= 0:
s += int(a[i]); i -= 1 # 加上 a 的当前位,指针左移
if j >= 0:
s += int(b[j]); j -= 1 # 加上 b 的当前位,指针左移
res.append(str(s & 1)) # 当前位 = s 的二进制最低位
carry = s >> 1 # 进位 = s 右移一位(除以 2)
return ''.join(reversed(res)) # 反转成高位到低位并拼接
print('67:', add_binary('11', '1')) # 期望 100
print('67:', add_binary('1010', '1011')) # 期望 10101
print('67:', add_binary('111', '111')) # 期望 1110
print('67 对照:', add_binary('1010', '1011') == bin(10 + 11)[2:]) # 期望 True
67: 100 67: 10101 67: 1110 67 对照: True