bitset

1 简介

作为一个专门存储二进制的容器，bitset 的每一个位置只能用来存储 (0,1) ，并且每一位只占一个 bit ，也就是说，每 (8) 位占一个字节，相比之下 bool 型一位 (1) 个字节，int 型一位 (4) 个字节。

2 声明

用 bitset 需要使用与其同名的头文件，同时我们可以用 string 类型来初始化 bitset ，像这样：

bitset<N> k(string("00010010"));

注意，在 bitset 中，最右边为第 (0)​ 位，以及 (N)​ 为 bitset 的长度，也就是说，最高到 (N-1)​ 位。

我们同样可以通过整型来赋值 bitset ，像这样：bitset<N> s(n) 。特别地，如果 (n) 的二进制位数超过 (N) ，我们就只取 (n) 后 (N) 位，即 (0) 到 (N-1) 位。

3 运算

bitset 支持左移，右移，以及所有的位运算：^,&,| ，不过，如果计算机字长为 (w)​​ ，那么这些操作的时间复杂度都是 (O(frac{N}{w}))​​ 。实际上 bitset 绝大部分的复杂度都为 (O(frac N w))​ ，而 (w) 一般为 (32) 。

同时 bitset 支持单点修改，直接用 [] 改某一位就可以。用 [] 也可以访问任意位置元素。

需要注意的是，左移并不会改变 bitset 的位数，也就是说，超过了最高位就不存储，低位补 (0)。

4 输入输出

我们直接使用 cin cout 就可以。

同时 bitset 可以转化成 string 类型和 unsigned int 类型，如果 bitset 大小大于 32 位，那么就会 RE 。

使用的函数是 to_string to_ulong ，代码：

s.reset();
s[2] = true;
unsigned int s1 = s.to_ulong();
std::cout << s1 << std::endl;                   //4
unsigned long long int s2 = s.to_ullong();      //C++11
std::cout << s2 << std::endl;                   //4
std::string ss = s.to_string();                 
std::cout << ss << std::endl;                   //00000100

5 常用成员函数

5.1 清空操作

s.reset() 将集合内所有元素清 (0)

5.2 赋值为 (1)

s.set() 在无参数时可以把所有位置赋值为 (1) 。

如果有参数，则参数形为 (int posi,bool val) 表示把第 (posi) 位赋值为 (val) ，其余为 (1) 。

5.3 返回某一位值

s.test(int posi) 返回第 (posi) 位的值。

5.4 是否有一位为 (1)

s.any() 返回一个 bool 值，如果这个 bitset 中有一位为 (1) ，那么返回 (1) 否则返回 (0) 。

5.5 是否每一位都为 (0)

s.none() 返回一个 bool 值，看 bitset 中是否每一位都为 (0) ，是则返回 (1) 否则返回 (0) 。

5.6 数 (1) 的个数

s.count() 返回一个 bitset 中 (1) 的个数。是一个无符号整型。

5.7 取反

函数 s.flip() 可以将集合内所有苏取反，如果引用参数 s.flip(int posi) ，那么就将第 (posi) 位取反。