位运算与位掩码状态 · HTML
数学 / 逻辑形态
mask∈[0,2^n)；第 i 位表示元素 i；sub=(sub-1)&mask 依次枚举非空子掩码。
识别信号
- n 很小且要看所有子集
- 选择状态是布尔集合
- 需快速并交差
- 容斥枚举性质子集
- 要枚举某集合全部子集
容易误判的相似信号
| Signal | Why it is different |
|---|
| n 较大 | 2^n 很快不可行，应找结构性剪枝或 DP 维度替代。 |
| 元素有高重数 | 一个 bit 只能表达是否存在，不能直接表达计数。 |
核心不变量
mask 与选择集合一一对应；位运算精确模拟集合并、交、删与包含。
状态、转移与处理顺序
| Item | Definition |
|---|
| State | 当前 mask、元素列表、可选 submask 与目标全掩码 full。 |
| Transition | 外层 mask 加一枚举所有集合；子掩码用 (sub-1)&mask 删除或重排最低有效位。 |
| Frontier / order | 数值顺序是编码前沿而非集合大小顺序；每个 n 位编码恰访问一次。 |
Python 骨架
def all_subsets(items):
n = len(items)
for mask in range(1 << n):
yield [items[i] for i in range(n) if mask >> i & 1]
def nonempty_submasks(mask):
sub = mask
while sub:
yield sub
sub = (sub - 1) & mask
def is_subset(a, b):
return a & b == a
正确性思路
- n 位二进制串与 n 元集合子集构成双射。
- range(2^n) 枚举每个编码一次，故不重不漏。
- sub-1 改变当前最低有效 1 及其低位，再与 mask 保证不引入集合外位。
- 该递推严格减小 sub，最终到 0。
复杂度
| Time | Space | Parameters |
|---|
| 全部子集 O(2^n n) 若物化；所有 mask 的所有 submask 总计 O(3^n) | O(n) 生成一个子集 | n 为可选元素数 |
边界条件
- 空集 mask=0 可能必须包含
- 1<<n 的增长极快
- 子掩码循环是否需要输出 0
- 重复 items 会产生位置不同但值相同集合
- 运算优先级加括号更清晰
错误模式
| Pattern | Why it fails / fix |
|---|
| 忘记空集 | range 从 1 开始会漏掉常见基例。 |
| 子掩码循环在 0 后继续 | 会回到 mask 形成死循环。 |
| 把数值顺序当大小顺序 | 相邻 mask 的 bit_count 不保证单调。 |
选择与排除规则
- n≈20 且必须全看：bitmask 枚举。
- 需要剪枝与输出解：回溯可能更自然。
- 状态还需最优值：bitmask DP。
- 枚举 mask 的子集时使用 submask 技巧而非再扫 2^n。
相关模板
原创微型例子
| 环节 | 内容 |
|---|
| Result | mask 5（二进制 101）代表选择 A 与 C。 |
| Scenario | 三种开关 A、B、C。 |
| Walkthrough | 第 0、2 位为 1；枚举 0..7 得到全部八种组合。 |
Recall prompts
我的补充