数据结构与算法 / 系统课时
用位掩码表示集合选择状态
用位掩码表示集合选择状态
当动态规划需要反复记录“哪些元素已经被选中”时,直接保存集合会让状态难以索引和比较。位掩码把每个元素映射到一个二进制位,使集合可以用一个整数表示,并通过位运算高效完成修改、判断与枚举。
学习目标
- 使用二进制位表示集合中元素的选中状态
- 掌握置位、清位、包含判断和子集枚举
- 根据 状态规模判断位掩码动态规划是否适用
一个整数如何表示一个集合
为 个元素编号 0 到 n - 1,让整数 mask 的第 i 位表示元素 i 是否被选择:该位为 1 表示已选择,为 0 表示未选择。例如有 4 个元素时,二进制 0101 表示元素 0 和元素 2 已被选择。
常用操作都可以直接由位运算完成:
| 目的 | 表达式 | 含义 |
|---|---|---|
| 置位 | mask | (1 << i) |
选择元素 i |
| 清位 | mask & ~(1 << i) |
取消元素 i |
| 判断包含 | (mask & (1 << i)) != 0 |
检查元素 i 是否已选择 |
| 翻转 | mask ^ (1 << i) |
切换元素 i 的选择状态 |
这样,集合相等可以直接比较两个整数,集合状态也能直接用作数组下标或哈希表键。
枚举一个掩码的所有子集
如果只需遍历 mask 的子集,不必扫描全部 0 到 2^n - 1。从 sub = mask 开始,不断执行 sub = (sub - 1) & mask,就能依次得到所有非空子掩码。
原因在于 sub - 1 会改变当前最低位附近的二进制结构,再与原始 mask 做按位与,就会删除所有不属于 mask 的位。整个过程只访问真正的子集状态。
可运行示例
下面同时演示集合修改、包含判断和标准子集枚举。为了便于观察,输出统一补齐为 4 位二进制。
def bits(mask, width=4):
return format(mask, f'0{width}b')
# 初始选择 A 和 C,对应第 0、2 位。
mask = (1 << 0) | (1 << 2)
print('initial=' + bits(mask))
mask |= 1 << 1
print('after_set_B=' + bits(mask))
mask &= ~(1 << 2)
print('after_clear_C=' + bits(mask))
print('has_B=' + str((mask & (1 << 1)) != 0))
# 枚举 1101 的全部非空子掩码。
base = 0b1101
subsets = []
sub = base
while sub:
subsets.append(bits(sub))
sub = (sub - 1) & base
print('subsets=' + ','.join(subsets))预期输出
initial=0101
after_set_B=0111
after_clear_C=0011
has_B=True
subsets=1101,1100,1001,1000,0101,0100,0001对子掩码枚举而言,顺序通常并不重要;重要的是每个非空子集恰好出现一次。如果还要包含空集,可以在循环结束后单独处理 0。
位掩码如何进入动态规划
最常见的状态写法是 dp[mask],表示恰好选择 mask 中这些元素后得到的最优值。若准备加入尚未选择的元素 i,新状态就是 next_mask = mask | (1 << i)。这样可以把原本难以直接索引的集合选择过程转化为整数状态转移。
但位掩码只记录“选了谁”,不会自动保存顺序、位置或最后一次选择。如果后续决策还依赖最后访问的元素,状态通常需要扩展为 dp[mask][last];如果还依赖额外资源数量,则还要增加相应维度。
状态规模决定适用范围
个二元选择一共有 个不同掩码,所以位掩码压缩的是状态表示方式,并没有消除指数级状态数。例如 时已有 1,048,576 个集合状态,而 时会增长到 33,554,432 个状态。
因此,O(2^n) 或 O(n2^n) 的算法常用于元素数量较小的组合问题;若转移还要枚举每个状态的所有子集,总复杂度可能进一步达到 。实际可承受范围取决于语言、状态大小和时间限制,不能只因为状态能塞进一个整数就认为算法足够快。
位掩码最适合“元素数量小、每个元素只有选或不选两种状态、转移频繁检查集合关系”的问题。判断是否使用它时,应同时检查状态能否完整表达未来决策,以及 级状态空间是否在资源预算内。