#include<bitset>

bitset 可看作一个多位二进制，每 $8$ 位占用 $1$ 个字节，相当于采用了状态压缩的二进制数组，并支持基本的位运算。

在估算程序运行的时间时，我们一般以 $32$ 位整数的运算次数为基准，因此 $n$ 位 bitset 执行一次位运算的复杂度可视为 $\frac{n}{32}$，效率较高。

声明

bitset < 10000 > s;

表示一个 $10000$ 位二进制数，< > 中填写位数。 下面把位数记为 $n$ 。

位运算操作符

~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