笔记

记录一些我经常忘的知识点

位运算

枚举特定集合的子集

• 设某个特定的 \(sup = (01101101)_2\)， 枚举出 \(sup\) 的所有子集。

从后往前枚举，用 \(sup\) 作为掩码。

int s = sup;
do {
    ... // 对子集的处理
    s = (s - 1) & sup;
} while(s != sup);

枚举大小为 \(k\) 的子集

• 枚举出所有 \(n = 7\)， \(k = 4\) 的子集。

变量	值	含义
s	\(0101110\)	当前枚举出来的集合
lb = s & -s	\(0000010\)	s 的 lowbit
left = s + lb	\(0110000\)	将 s 最右端连续的 \(1\) 区间都变成 \(0\)，然后在区间左边补一个 \(1\)
right = (s & ~left) / lb >> 1	\(0000011\)	将 s 最右端连续的 \(1\) 区间不断右移，直到 \(1\) 的数量减少一个
s = left | right	\(0110011\)	下一个枚举出来的集合

for(int s = (1 << k) - 1; s < 1 << n; )
{
    ... // 对子集的处理
    int lb = s & -s, left = s + lb, right = (s & ~left) / lb >> 1;
    s = left | right;
}

---

最后更新: 2024-03-04
创建日期: 2024-01-04