位运算与状态压缩：从集合枚举到高效判重的工程技巧

位运算与状态压缩从集合枚举到高效判重的工程技巧一、集合操作的效率陷阱O(n) 判重 vs O(1) 位判重算法竞赛和工程实践中集合的判重、交集和子集枚举是高频操作。使用哈希集合或数组进行判重单次操作时间复杂度为 O(n) 或 O(1) 但常数较大。当集合大小固定且元素范围有限时如 20 个以内的元素位运算可以将集合表示为整数判重和交集操作降至 O(1) 且常数极小。某状态空间搜索算法在 n20 的场景下使用哈希集合判重耗时 3.2 秒改用位运算后降至 0.4 秒性能提升 8 倍。状态压缩State Compression的核心思想是用整数的二进制位表示集合位运算替代集合操作。二、位运算与状态压缩的核心操作flowchart LR subgraph 集合操作[集合操作 → 位运算映射] A[添加元素 i] -- A1[S | (1 i)] B[删除元素 i] -- B1[S ~(1 i)] C[判断元素 i 是否在集合中] -- C1[S (1 i)] D[集合交集] -- D1[S1 S2] E[集合并集] -- E1[S1 | S2] F[集合差集] -- F1[S1 ~S2] G[枚举所有子集] -- G1[sub (sub-1) S] end style 集合操作 fill:#efe,stroke:#333三、状态压缩的代码实现与应用from typing import Callable class Bitset: 位集合工具类 staticmethod def add(s: int, i: int) - int: 添加元素 i 到集合 return s | (1 i) staticmethod def remove(s: int, i: int) - int: 从集合中删除元素 i return s ~(1 i) staticmethod def contains(s: int, i: int) - bool: 判断元素 i 是否在集合中 return bool(s (1 i)) staticmethod def size(s: int) - int: 集合大小popcount return bin(s).count(1) staticmethod def intersect(s1: int, s2: int) - int: 交集 return s1 s2 staticmethod def union(s1: int, s2: int) - int: 并集 return s1 | s2 staticmethod def difference(s1: int, s2: int) - int: 差集在 s1 但不在 s2 return s1 ~s2 staticmethod def enumerate_subsets(s: int) - list[int]: 枚举集合 s 的所有非空子集 subsets [] sub s while sub: subsets.append(sub) sub (sub - 1) s return subsets staticmethod def lowest_bit(s: int) - int: 取最低位的 1lowbit return s (-s) staticmethod def enumerate_bits(s: int) - list[int]: 枚举集合中所有元素的索引 bits [] while s: lb s (-s) bits.append(lb.bit_length() - 1) s ^ lb return bits # 应用1旅行商问题TSP状态压缩 DP def tsp_dp(dist: list[list[int]], n: int) - int: 旅行商问题状态压缩 DP dp[mask][i] 经过 mask 中的城市最后在 i 的最短路径 mask 用二进制位表示已访问的城市集合 INF float(inf) full_mask (1 n) - 1 # dp[mask][i]已访问城市集合为 mask当前在城市 i dp [[INF] * n for _ in range(1 n)] dp[1][0] 0 # 从城市 0 出发只访问了城市 0 for mask in range(1, 1 n): for u in range(n): if dp[mask][u] INF: continue if not (mask (1 u)): continue # 尝试访问下一个未访问的城市 for v in range(n): if mask (1 v): continue # 已访问过 new_mask mask | (1 v) new_dist dp[mask][u] dist[u][v] if new_dist dp[new_mask][v]: dp[new_mask][v] new_dist # 回到起点 result INF for u in range(1, n): if dp[full_mask][u] dist[u][0] result: result dp[full_mask][u] dist[u][0] return result # 应用2N 皇后问题位运算优化 def n_queens_bit(n: int) - int: N 皇后问题位运算加速 用三个整数表示列、主对角线、副对角线的攻击范围 count 0 def backtrack(row: int, cols: int, diag1: int, diag2: int): nonlocal count if row n: count 1 return # 当前行可放置的位置不在任何攻击范围内 available ((1 n) - 1) ~(cols | diag1 | diag2) while available: # 取最低位的 1即最右边的可用位置 pos available (-available) available ^ pos # 移除该位置 # 递归下一行更新攻击范围 backtrack( row 1, cols | pos, # 列攻击 (diag1 | pos) 1, # 主对角线左移 (diag2 | pos) 1, # 副对角线右移 ) backtrack(0, 0, 0, 0) return count # 应用3依赖关系判重 def check_circular_dependency( n: int, deps: list[tuple[int, int]] ) - list[int]: 检测循环依赖状态压缩 DFS deps: [(a, b)] 表示 a 依赖 b 返回参与循环的节点列表 graph [[] for _ in range(n)] for a, b in deps: graph[a].append(b) visited 0 # 已访问节点位集 in_stack 0 # 当前路径上的节点位集 cycle_nodes [] def dfs(u: int) - bool: nonlocal visited, in_stack, cycle_nodes visited | (1 u) in_stack | (1 u) for v in graph[u]: if not (visited (1 v)): if dfs(v): if in_stack (1 v): cycle_nodes.append(v) return True elif in_stack (1 v): cycle_nodes.append(v) return True in_stack ~(1 u) return False for i in range(n): if not (visited (1 i)): dfs(i) return cycle_nodes # 应用4权限系统位掩码 class PermissionSystem: 基于位掩码的权限系统 # 定义权限位 READ 1 0 # 0b0001 WRITE 1 1 # 0b0010 EXECUTE 1 2 # 0b0100 ADMIN 1 3 # 0b1000 def __init__(self, permissions: int 0): self.permissions permissions def grant(self, perm: int): 授予权限 self.permissions | perm def revoke(self, perm: int): 撤销权限 self.permissions ~perm def has(self, perm: int) - bool: 检查权限 return bool(self.permissions perm) def has_all(self, perms: int) - bool: 检查是否拥有所有指定权限 return (self.permissions perms) perms def has_any(self, perms: int) - bool: 检查是否拥有任一指定权限 return bool(self.permissions perms)四、状态压缩的 Trade-offs元素范围限制。状态压缩仅适用于元素范围有限通常 ≤ 20-60的场景。Python 整数无上限但 n60 时状态空间达 2^60远超内存容量。C 中 64 位整数最多支持 64 个元素。可读性下降。位运算代码的可读性远低于集合操作。s (1 i)不如i in set直观。建议封装工具类如 Bitset业务代码使用语义化方法名。调试困难。整数表示的集合难以直接打印和调试。建议实现to_string()方法将位集合转换为可读的元素列表。与哈希集合的适用边界。当元素范围超过 60 或需要动态增删元素时哈希集合更合适。状态压缩的优势仅在元素范围小、操作密集的场景下才显著。五、总结状态压缩通过将集合映射为整数的二进制位将集合操作转化为 O(1) 的位运算在元素范围有限的场景下提供极致性能。核心应用包括TSP 等状态压缩 DPmask 表示已访问集合、N 皇后等回溯加速位掩码表示攻击范围、循环依赖检测位集表示访问状态、权限系统位掩码表示权限组合。但元素范围限制、可读性下降和调试困难要求在工程中使用时做好封装和文档。