集合&位运算

引言

常见位运算操作总结。

场景

主要有以下使用场景：

1. 子集枚举
2. 状压DP
3. 优化元素量少的集合运算
4. 异或场景（e.g. 消除成对的元素）

集合操作

操作都以python举例。

基本操作

# 集合大小
s.bit_count()

# 二进制长度
s.bit_length()

# 集合最大元素
s.bit_length()-1

# 集合最小元素
(s&-s).bit_length-1

这里对最小元素的计算进行说明： -s = (~s)+1 而这个操作会对最后一个1之前的元素取反，所以交集之前的集合会只保留最后一个元素。

遍历

假设集合范围为0 ~ n-1，枚举范围元素i，判断i是否在集合中：

for i in range(n):
    if (s >> i) & 1: # i在s中
        # 其他逻辑

直接遍历s中元素，通过不断计算最小元素的方式：

t = s
while t:
    lowbit = t & -t
    t ^= lowbit
    i = lowbit.bit_length() - 1
    # 处理 i 的逻辑

枚举

元素范围0 ~ n-1，从空集枚举到全集：

for s in range(1 << n):
    # 处理 s 的逻辑

枚举集合s的所有非空子集sub：

sub = s
while sub:
    # 处理 sub 的逻辑
    sub = (sub - 1) & s

为什么是(sub - 1) & s： 因为sub-1本质是将最后一位1以及后面的位数反转，但是这样会引入多余的1，所以要对原本的集合取并集。

如果包括空集：

sub = s
while True:
    # 处理 sub 的逻辑
    if sub == 0:
        break
    sub = (sub - 1) & s

超集： 即全集即t的子集。

s = t
while s < (1 << n):
    # 处理 s 的逻辑
    s = (s + 1) | t