從零開始的數據結構教程（八）位運算與狀態壓縮

🎩 標題一：位運算基礎——魔術師的二進制手套

位運算是一種直接操作數字二進制位的運算方式，它高效且巧妙，就像魔術師戴上了二進制手套，能夠精準地操控每一個比特。理解位運算是深入學習狀態壓縮和其他底層優化技巧的基礎。

六大核心操作符

假設我們有兩個初始數字：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) 實現