17370845950

bitset是C++中用于处理固定长度二进制序列的类模板，定义在头文件中，支持多种初始化方式（整数、字符串、拷贝），提供count()、test()、set()等成员函数及位运算操作符，适用于状态压缩、汉明距离计算和筛法优化等场景，但大小需在编译时确定，超出to_ulong/to_ullong范围会抛出异常，输入输出需匹配位数且仅含0/1字符。

在C++中，bitset 是一个非常实用的类模板，定义在 头文件中，用于高效地处理固定长度的二进制位序列。它不仅简化了位运算操作，还提供了直观的接口来访问和修改每一位，非常适合用于状态压缩、集合表示、位图标记等场景。

1. bitset 基本定义与初始化

bitset 的大小必须在编译时确定，声明方式如下：

其中 N 是位数。支持多种初始化方式：

• bitset b1(255); —— 用整数初始化（转为二进制）
• bitset b2("11001100"); —— 用字符串初始化
• bitset b3(b1); —— 拷贝构造

注意：字符串只能包含 '0' 和 '1'，否则会抛出 std::invalid_argument 异常。

2. 常用成员函数与操作符

bitset 提供了丰富的接口来操作和查询位状态：

• count()：返回值为1的位的数量（即二进制中1的个数）
• size()：返回总位数
• test(i)：检查第 i 位是否为1（越界会抛异常）
• any()：是否有任意一位为1
• none()：是否所有位都为0
• set(i)：将第 i 位置1；set() 全部置1
• reset(i)：将第 i 位置0；reset() 全部清零
• flip(i)：翻转第 i 位；flip() 翻转所有位
• to_ulong()：转换为 unsigned long
• to_ullong()：转换为 unsigned long long

支持常见的位运算操作符：&（与）、|（或）、^（异或）、~（非）、、>>。

3. 实际应用技巧与优化

使用 bitset 可以显著提升某些算法效率，尤其是在空间和时间敏感的场景中。

状态压缩示例：比如在动态规划中表示集合状态：

可表示最多20个元素的子集，比布尔数组更省空间。

快速计算汉明距离（两个数对应位不同的数量）：

比循环逐位判断快得多。

筛法优化：用 bitset 实现埃拉托斯特尼筛法，节省内存：

4. 注意事项与限制

bitset 的大小必须是编译时常量，不能动态改变。如果需要可变长度的位容器，应考虑 std::vector 或第三方库。

超出 to_ulong/to_ullong 范围的 bitset 会抛出 std::overflow_error。

虽然 bitset 支持流输入输出：