位运算通过位掩码高效实现集合操作，适用于元素为0到63的小规模非负整数集，用二进制位表示元素存在性，支持并（|）、交（&）、差（&~）、补（~）等操作，结合__builtin_popcount、lowbit等技巧可优化状态压缩DP与组合枚举，需注意范围限制与无符号类型使用。
在C++中，位运算是一种高效处理集合操作的技术，尤其适用于元素数量有限且较小的场景。通过将集合映射为整数中的二进制位（称为“位掩码”），我们可以用简单的位操作实现并、交、差、补等集合运算，速度远超传统容器如set或vector。
使用位掩码表示集合
假设集合中的元素是0到31之间的整数，可以用一个32位int或unsigned int来表示整个集合。每一位对应一个元素是否存在：1表示存在，0表示不存在。
例如，集合 {0, 2, 5} 可以表示为：
bit: ... 5 4 3 2 1 0
... 1 0 0 1 0 1
对应的数值是：1 << 0 | 1 << 2 | 1 << 5，即 1 + 4 + 32 = 37。
立即学习“C++免费学习笔记（深入）”；
基本集合操作的位运算实现
以下是一些常见集合操作及其对应的位运算：
-
并集（A ∪ B）：使用按位或
a | b -
交集（A ∩ B）：使用按位与
a & b -
差集（A - B）：使用按位与非
a & ~b -
补集（~A）：使用按位取反
~a（注意范围限制） -
判断是否包含元素x：
(a & (1 << x)) != 0 -
添加元素x：
a |= (1 << x) -
删除元素x：
a &= ~(1 << x) -
检查是否为空集：
a == 0 - 枚举所有子集：循环从0到(1<<n)-1即可遍历n个元素的所有子集
优化技巧与实际应用
位运算不仅快，还能结合一些技巧提升效率：
-
计算集合大小（popcount）：使用内建函数
__builtin_popcount(a)快速统计二进制中1的个数，即集合元素个数。对于long long可用__builtin_popcountll()。 -
获取最低位的1：
lowbit = a & (-a)，可用于逐个提取集合中的元素。 -
遍历集合中所有元素：
<font face="Courier New"> while (mask) { int x = __builtin_ctz(mask); // 获取最低位1的位置 // 处理元素 x mask &= mask - 1; // 清除最低位的1 } </font> -
枚举某个集合的所有子集：
<font face="Courier New"> for (int sub = s; sub; sub = (sub - 1) & s) { // 处理子集 sub } // 别忘了空集：sub == 0 的情况 </font>
这类技巧常用于状态压缩DP（状压DP）、组合搜索、图论中的独立集/团枚举等问题，能显著减少常数时间和代码复杂度。
注意事项与局限性
位运算实现集合操作虽快，但有其适用边界：
- 元素范围不能太大，一般不超过64（使用
unsigned long long时） - 只适合非负整数作为元素，不支持任意类型
- 调试时不易直观查看内容，建议封装打印函数辅助调试
- 注意符号位问题，尽量使用
unsigned类型避免未定义行为
基本上就这些。掌握位掩码和位运算技巧后，很多集合类问题可以写出更简洁高效的代码。关键是理解“一位代表一元素”的思想，并熟练运用常见的位操作模式。不复杂但容易忽略细节，比如边界和数据类型选择。
