Update 2025-12-30

为了更好理解和应用 bitset 于是更新了教程。

1.什么是 bitset

bitset 是 C++STL 中的一种容器类，方便表示和操作固定长度的二进制数。

• 头文件 <bitset>

• 定义的时候指定二进制个数（长度 N）, 例如 bitset<100>a ,定义了一个 长度为 100 的二进制序列 a

• bitset 中每一位只能是 0 或 1

• 长度为 $N$ 的 bitset , 空间复杂度为 $O(\frac{N}{8})$

2.为什么需要定义 bitset

int 和 long long 只能状压表示 32/64 位状态，如果需要状压表示更长的状态属性(状态属性只有两种)，那么就可以使用 bitset

3. 常用函数

• 构造函数 (定义变量自动运行)

  • bitset(): 每一位都是 false。
  • bitset(unsigned long val): 设为 val 的二进制形式。例如，bitset<8> a(7) , 表示定义并初始化为二进制 00000111;
  • bitset(const string& str): 设为 01 串 str。例如， bitset<8> a("01011"), a 就初始化为 00001011 , 从低位开始初始化.

• 成员函数

以下表格 ，定义 bitset<4>a("0101")；

4. 位运算符

bitset 支持的位运算符：

示例：

bitset<4> a("1100"), b("1010");
cout << (a & b) << endl;  // 1000
cout << (a | b) << endl;  // 1110
cout << (a ^ b) << endl;  // 0110
cout << (~a) << endl;     // 0011
cout << (a >> 1) << endl; // 0110

之前的教程

位运算操作符

~s: 返回对 bitset s 按位取反的结果。

&,|,^ : 返回对每个位数相同的 bitset 执行按位与、或、异或运算的结果。

>>,<<: 返回把一个 bitset 右移、左移若干位的结果。

==,!=: 比较两个 bitset 代表的二进制数是否相等。

[ ] 操作符

s[k] 表示 s 的第 k 位，既可以取值，也可以赋值。

在 $10000$ 位二进制数中，最低位为 s[0]，最高位为 s[9999].

count()

s.count() 返回有多少位为 $1$ 。

any()/none()

若 s 所有位都为 0 ，则 s.any() 返回 false , s.none() 返回 true.

若 s 至少一位为 1，则 s.any() 返回 true , s.none() 返回 false.

set()/reset()/flip()

s.set() 把 s 所有位变为 1 。

s.set(k,v) 把 s 的第 k 位改为 v，即 s[k]=v。

s.reset() 把 s 所有位变为 0。

s.reset(k) 把 s 的第 k 位改为 0 ，即 s[k]=0 。

s.flip() 把 s 的所有位取反， 即 s=~s 。

s.flip(k) 把 s 的第 k 位取反，即 s[k]^=1。

学习完毕

{{ select(1) }}

• YES
• NO