C++ bitset位集合用法_C++二进制操作与状态压缩技巧

在C++中，bitset 是一个非常实用的模板类，用于高效地操作固定长度的二进制位序列。它定义在 bits/stdc++.h 或 <bitset> 头文件中，适合处理位运算、状态压缩、集合表示等问题。相比手动使用整型变量进行位操作，bitset 提供了更直观、安全和易读的接口。

bitset 基本定义与初始化

bitset 的模板参数是编译期确定的常量，表示位数：

• bitset<8> bs1; // 默认初始化为全0
• bitset<8> bs2(255); // 用整数初始化（十进制）
• bitset<8> bs3("11001010"); // 用字符串初始化
• bitset<16> bs4 = bitset<16>(0xFF); // 十六进制也支持

注意：字符串初始化时只能包含 '0' 和 '1'，否则会抛出异常。超出位宽的部分会被截断，不足则高位补0。

常用成员函数与操作符

bitset 支持多种便捷的操作方法，让位操作更清晰：

立即学习“C++免费学习笔记（深入）”；

• count()：返回1的个数（即汉明权重）
• size()：返回总位数
• test(i)：检查第 i 位是否为1（越界会抛异常）
• set(i)：将第 i 位置为1；set(i, 0) 可清零
• reset(i)：将第 i 位置为0；reset() 全部清零
• flip()：翻转所有位；flip(i) 翻转第 i 位
• any()：是否有任意一位为1
• none()：是否全为0
• to_ulong() / to_ullong()：转换为 unsigned long / unsigned long long
• [] 操作符：可像数组一样访问某一位（只读或赋值）

例如：

二进制操作与位运算支持

bitset 支持常见的按位运算，语法清晰：

Medeo

AI视频生成工具

191

查看详情

• ~bs：取反
• bs1 & bs2：按位与
• bs1 | bs2：按位或
• bs1 ^ bs2：按位异或
• bs << n、bs >> n：左右移位

这些运算要求两个 bitset 的大小相同，否则编译报错。结果仍是一个 bitset，便于链式操作。

状态压缩中的实际应用

在动态规划或搜索问题中，常使用状态压缩来表示集合状态，比如“哪些物品已被选”或“哪些节点已访问”。用 int 或 long long 配合位运算虽然高效，但不易调试。bitset 能提升代码可读性。

例如：n 个城市旅行商问题（TSP）简化版，可用 bitset 表示已访问城市集合：

虽然 bitset 不支持运行时动态改变大小，但对大多数状态压缩场景来说，最大状态数是已知的，因此完全可以胜任。

基本上就这些。bitset 让位操作更安全、直观，尤其适合算法竞赛和状态管理。虽然性能略低于直接位运算，但在可接受范围内，且大幅提高开发效率和代码清晰度。合理使用，能让你的 C++ 位操作既高效又优雅。