数据结构与算法 / 系统课时

用位掩码表示集合选择状态

用位掩码表示集合选择状态

当动态规划需要反复记录“哪些元素已经被选中”时,直接保存集合会让状态难以索引和比较。位掩码把每个元素映射到一个二进制位,使集合可以用一个整数表示,并通过位运算高效完成修改、判断与枚举。

学习目标

  • 使用二进制位表示集合中元素的选中状态
  • 掌握置位、清位、包含判断和子集枚举
  • 根据 2n2^n 状态规模判断位掩码动态规划是否适用

一个整数如何表示一个集合

为 nn 个元素编号 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 位二进制。

python
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))

预期输出

text
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];如果还依赖额外资源数量,则还要增加相应维度。

状态规模决定适用范围

nn 个二元选择一共有 2n2^n 个不同掩码,所以位掩码压缩的是状态表示方式,并没有消除指数级状态数。例如 n=20n=20 时已有 1,048,576 个集合状态,而 n=25n=25 时会增长到 33,554,432 个状态。

因此,O(2^n) 或 O(n2^n) 的算法常用于元素数量较小的组合问题;若转移还要枚举每个状态的所有子集,总复杂度可能进一步达到 O(3n)O(3^n)。实际可承受范围取决于语言、状态大小和时间限制,不能只因为状态能塞进一个整数就认为算法足够快。

位掩码最适合“元素数量小、每个元素只有选或不选两种状态、转移频繁检查集合关系”的问题。判断是否使用它时,应同时检查状态能否完整表达未来决策,以及 2n2^n 级状态空间是否在资源预算内。

按自己的节奏,确认真正理解。

目录与阅读设置

阅读设置

17

记录一个想法

用位掩码表示集合选择状态

0 / 10000 · 笔记保存到账号。未提交的修改会在关闭、离开或刷新后丢失。

登录哪都通