bitset教程

Bitset

在 STL 中有一个好用的结构叫做 bitset，今天学习其相关运用。

bitset 是一个由位（bit）组成的数组，每个位可以是 0 或者 1。和数组一样从 0 开始，每个元素都能单独访问，下标编号为 [0,N)。bitset 的大小在编译时就需要确定，如果你想要不确定长度的，请使用 vector<bool>。

1. 定义

bitset<N> b;

初始化 bitset：

b=bitset<N>(value);
//value可以为string或者int

2. count() 函数：返回1的数量

int n=b.count();

3. any() 函数：是否含有1

if(b.any()) cout<<"含有1";
else cout<<"不含1";

4. none() 函数：是否不含1

if(b.none()) cout<<"不含1";
else cout<<"含有1";

5. all() 函数：是否全为1

if(b.all()) cout<<"全为1";
else cout<<"不全为1";

6. set() 函数：设置所有位为1

b.set();

7. set(pos,val) 函数：设置指定位置为指定值

b.set(3,0);

8. reset() 函数：设置所有位为0

b.reset();

9. flip() 函数：取反所有位

b.flip();

10. flip(pos) 函数：取反指定位

b.flip(2);

11. test(pos) 函数：指定位是否为1

if(b.test(2)) cout<<"第2位为1";

12. to_string() 函数：将bitset转换为字符串

string s=b.to_string();

bitset整体运算

bitset 的运算就像一个普通整数一样，可以进行位运算。

bitset<4> b1("1100");
bitset<4> b2("1010");
b1^=b2;
b1|=b2;
b1&=b2;
b1>>1;
b1<<1;

进行单点修改时，直接访问位置赋值即可，时间复杂度 O(1)：

s[pos]=x;

输入如果不足 N 个，会从第 0 位开始赋值；大于 N 个，会截断前 N 个。输出时 bitset 是反着输出的，会先输出第 N-1 个，接着依次。

cin>>b;
cout<<b;