从零开始的数据结构教程（八）位运算与状态压缩

🎩 标题一：位运算基础——魔术师的二进制手套

位运算是一种直接操作数字二进制位的运算方式，它高效且巧妙，就像魔术师戴上了二进制手套，能够精准地操控每一个比特。理解位运算是深入学习状态压缩和其他底层优化技巧的基础。

六大核心操作符

假设我们有两个初始数字：x = 5（二进制 0101）和 y = 3（二进制 0011）。

x & y：按位与 (AND) → 0001 (1)
- 规则：只有对应的两个二进制位都为 1 时，结果位才为 1。
- 应用：清零特定位、判断某位是否为 1（x & (1 << i)）。
x | y：按位或 (OR) → 0111 (7)
- 规则：对应的两个二进制位中只要有一个为 1，结果位就为 1。
- 应用：设置特定位为 1（x | (1 << i)）。
x ^ y：按位异或 (XOR) → 0110 (6)
- 规则：对应的两个二进制位不同时，结果位为 1。
- 应用：翻转特定位（x ^ (1 << i)）、不使用额外变量交换两个数、寻找数组中唯一出现的数字。
~x：按位取反 (NOT) → 1010 (-6)
- 规则：将所有二进制位 0 变为 1，1 变为 0。
- 注意：对于有符号整数，结果是其补码表示，这通常会导致负数。
x << 1：左移 (Left Shift) → 1010 (10)
- 规则：将 x 的所有二进制位向左移动 1 位，低位补 0。
- 应用：相当于乘以 $2^1$ （x << n 相当于 $\times 2^n$ ）。
x >> 1：右移 (Right Shift) → 0010 (2)
- 规则：将 x 的所有二进制位向右移动 1 位，高位补 0（对于无符号数）或补符号位（对于有符号数）。
- 应用：相当于除以 $2^1$ 并向下取整（x >> n 相当于 $\div 2^n$ ）。

高频技巧

判断奇偶：

# 如果 x 的最低位是 1，则 x 是奇数
x & 1 == 1

取最低位的 1 (lowbit)：
- lowbit = x & -x：这个技巧利用了负数的补码表示，能够有效地提取出 x 二进制表示中最右边的 1 及其后面的 0。
- 例如：x = 6 (0110)，-x 在补码中是 1010。
  6 & -6 (0110 & 1010) → 0010 (2)。
- 应用：树状数组 (Fenwick Tree)、某些优化算法。
消去最低位的 1：
- x &= x - 1：每次执行这个操作，都会将 x 二进制表示中最右边的 1 变为 0。
- 例如：x = 6 (0110)，x - 1 是 5 (0101)。
  6 & 5 (0110 & 0101) → 0100 (4)。
- 应用：计算一个数二进制中 1 的个数 (汉明重量)。

🧩 标题二：状态压缩——用数字表示集合

状态压缩是一种巧妙的技巧，它利用二进制位的特性，将一个集合或一组布尔状态压缩成一个整数。每个二进制位代表一个元素的“存在”或“不存在”、“已选”或“未选”。

场景比喻

想象你有一组物品 {A, B, C}。你可以用三位二进制数来表示这些物品的状态：

最低位代表 A (001)
中间位代表 B (010)
最高位代表 C (100)

那么，集合 {A, C} 就可以被表示为二进制 101，其十进制值为 5。

集合操作

假设 S = 0b101（表示集合 {A, C}）。

添加元素 B：将第 1 位（从右往左数，0-indexed）设置为 1。
```
S |= (1 << 1) # S → 0b111 (7)，表示集合 {A, B, C}
```

移除元素 A：将第 0 位设置为 0。

S &= ~(1 << 0) # S → 0b110 (6)，表示集合 {B, C}

检查元素 C 是否存在：

if S & (1 << 2): # S 为 0b110，(1 << 2) 为 0b100。 0b110 & 0b100 → 0b100 (非零)print("C 存在")

经典例题：旅行商问题 (TSP)

旅行商问题是一个 NP 难问题，但对于小规模问题，可以使用状态压缩动态规划来解决。

问题：给定 n 个城市和城市之间的距离，从一个城市出发，访问每个城市一次，最后回到起始城市，求最短的总距离。

def tsp(dist):n = len(dist) # 城市数量# dp[mask][u] 表示：已经访问过的城市集合为 mask，且当前停留在城市 u 的最短路径长度# mask 是一个二进制数，其中第 i 位为 1 表示城市 i 已访问dp = [[float('inf')] * n for _ in range(1 << n)]# 初始化：从城市 0 出发，只访问了城市 0，停留在城市 0，路径长度为 0dp[1][0] = 0 # 1 << 0 是 1 (二进制 00...01)，表示只访问了城市 0# 遍历所有可能的状态 (mask)# mask 从 1 开始，到 (1 << n) - 1 (即所有城市都访问过的状态)for mask in range(1, 1 << n):# 遍历当前状态 mask 下，可能停留的城市 ufor u in range(n):# 确保城市 u 在 mask 中 (即城市 u 已经被访问过)if not (mask & (1 << u)):continue # 如果城市 u 不在 mask 中，则跳过# 遍历所有可能的下一个城市 vfor v in range(n):# 如果城市 v 已经在 mask 中 (即城市 v 已经被访问过)，则跳过if mask & (1 << v):continue# 如果从城市 u 到城市 v 的距离是有效的 (不是无穷大)if dist[u][v] == float('inf'):continue# 计算新的 mask (包含了城市 v)new_mask = mask | (1 << v)# 更新 dp[new_mask][v]：# 从 dp[mask][u] 加上从 u 到 v 的距离dp[new_mask][v] = min(dp[new_mask][v], dp[mask][u] + dist[u][v])# 最终结果：# 遍历所有“所有城市都访问过”的状态 (mask = (1 << n) - 1)# 找到从某个城市 u 结束，再回到起始城市 0 的最短路径min_total_dist = float('inf')full_mask = (1 << n) - 1 # 所有城市都被访问过的 maskfor u in range(n):if dist[u][0] != float('inf'): # 确保能从 u 返回城市 0min_total_dist = min(min_total_dist, dp[full_mask][u] + dist[u][0])return min_total_dist# 示例：4个城市，距离矩阵
# dist[i][j] 表示从城市 i 到城市 j 的距离
# 注意：如果两个城市之间没有直达路径，可以表示为 float('inf')
# 城市 0 -> 1 -> 2 -> 3 -> 0
# 0-1: 10, 0-2: 15, 0-3: 20
# 1-0: 10, 1-2: 35, 1-3: 25
# 2-0: 15, 2-1: 35, 2-3: 30
# 3-0: 20, 3-1: 25, 3-2: 30
# 这是一个对称矩阵的例子，实际可能不对称
# 距离矩阵示例 (4个城市)
# from math import inf
# distances = [
#     [0, 10, 15, 20],
#     [10, 0, 35, 25],
#     [15, 35, 0, 30],
#     [20, 25, 30, 0]
# ]
# print(tsp(distances)) # 预期输出 80 (0->1->3->2->0 的路径)

⚡ 标题三：位运算实战——布隆过滤器与汉明重量

位运算在实际工程中有很多高效的应用，特别是在数据去重、统计等场景。

布隆过滤器 (Bloom Filter) 原理

概念：一种空间效率极高的概率型数据结构，用于判断一个元素是否可能存在于一个集合中。它允许一定程度的误判（“存在”可能实际上不存在），但绝不会误判（“不存在”就一定不存在）。
工作方式：
1. 初始化一个所有位都为 0 的位数组（或称位图）。
2. 当添加元素时，通过多个独立的哈希函数将元素映射到位数组中的多个位置，并将这些位置的位设置为 1。
3. 当查询元素时，再次通过这些哈希函数计算出对应的位位置。如果所有这些位置的位都为 1，则认为该元素可能存在；只要有一个位为 0，则该元素一定不存在。
应用场景：
- 海量数据去重：如网页爬虫判断 URL 是否已爬取。
- 快速判断黑名单：如垃圾邮件过滤、防止缓存穿透。

汉明重量 (Hamming Weight) / 位计数

问题：计算一个无符号整数的二进制表示中 1 的个数（LeetCode 191）。

def hammingWeight(n: int) -> int:count = 0# 循环直到 n 变为 0while n:# 每次执行 n &= (n - 1) 都会消去 n 最右边的 1n &= (n - 1)count += 1return count# 示例
# print(hammingWeight(11)) # 11 (00001011) -> 3
# print(hammingWeight(6))  # 6 (00000110) -> 2

应用场景：
- 特征去重：为用户行为、内容等生成二进制指纹，通过汉明距离（两个数字二进制位不同的数量）判断相似度。
- 数据压缩、密码学等领域。

🃏 标题四：状态压缩 DP——扑克牌游戏策略

状态压缩不仅可以用于表示集合，还可以用于表示游戏或其他问题的状态，进而结合动态规划解决一些博弈论问题或复杂搜索问题。

例题：翻转游戏 (LeetCode 293)

问题：给定一个只包含 '+' 和 '-' 的字符串 s。你可以进行任意次操作：选择两个连续的 ++ 并将它们翻转成 --。无法进行任何操作的人输。假设你是先手，判断你是否能赢。

def canWin(s: str) -> bool:memo = {} # 使用备忘录存储已计算过的字符串状态，避免重复计算# dfs 函数：判断在当前字符串 s 的状态下，先手玩家能否赢def dfs(current_s):if current_s in memo: # 如果当前状态已经计算过，直接返回结果return memo[current_s]# 遍历所有可能的翻转操作for i in range(len(current_s) - 1):if current_s[i:i+2] == "++": # 找到可以翻转的 "++"# 尝试进行翻转，生成新状态next_s = current_s[:i] + "--" + current_s[i+2:]# 递归调用 dfs(next_s)，判断对手在 next_s 状态下能否赢# 如果对手不能赢 (即 `not dfs(next_s)` 为 True)，# 那么当前玩家就能赢if not dfs(next_s):memo[current_s] = True # 标记当前状态为可赢return True # 找到一个赢的路径，立即返回# 如果遍历完所有可能的翻转操作，都没有找到能赢的路径memo[current_s] = False # 标记当前状态为不可赢return Falsereturn dfs(s) # 从初始字符串开始判断

状态压缩优化：如果字符串长度较小，可以将字符串 s 转换为一个二进制数（例如，'+' 为 1，'-' 为 0），这样就可以用整数来作为 memo 的键，进一步提高效率和空间利用率。这种问题通常被称为“状态压缩 DP”或“记忆化搜索”。

📊 总结表：位运算魔法手册

技巧	代码实现示例	应用场景
集合表示	`mask = (1 << i)	(1 << j)`
快速幂	`x <<= 1` 代替 `x *= 2`	数值计算加速，在底层库中常见
交换变量	`a ^= b; b ^= a; a ^= b`	不使用额外空间交换两个变量的值
找不同数字	`xor = reduce(lambda x,y:x^y, nums)`	LeetCode 136 (只出现一次的数字)
判断奇偶	`x & 1 == 1`	效率高于 `x % 2 != 0`
消去最低位1	`n &= (n - 1)`	计算汉明重量 (二进制中 `1` 的个数)
获取最低位1	`lowbit = x & -x`	树状数组 (Fenwick Tree) 实现