位运算技巧分类总结

学习笔记 评论

从集合论到位运算，常见位运算技巧分类总结！

1.集合与集合

2.集合与元素

3.遍历集合

设元素范围从 00到 n−1n-1，挨个判断每个元素是否在集合 ss中：

1
2
3
for i in range(n):
    if (s >> i) & 1:  # i 在 s 中
        # 处理 i 的逻辑

4.枚举集合

设元素范围从 00到 n−1n-1，从空集∅\empty枚举到全集UU:

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

从大到小枚举所有非空子集：

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

5.练习

位运算练习:

状态压缩 DP。这类题目通常和排列/子集有关，可以先从暴力回溯开始思考，再过渡到记忆化搜索和递推。

GladdduckKB Master

我写的个人简介。