STL应用 —— bitset

STL应用 —— bitset

bitset是一个多位二进制数，如同状态压缩的二进制数。使用bitset时，需要引入头文件#include。“bitset<1000>s;”表示定义一个1000位的二进制数s 。

【基本的位运算】

• ~ 取反
• & 与
• | 或
• ^ 异或
• >> 右移
• << 左移
• == 相等比较
• != 不相等比较

【一些操作】

可以通过“[ ]”操作符直接得到第k 位的值

也可以通过赋值操作改变该位的值。例如s [k ]=1，表示将二进制数s 的第k 位置1。
需要注意的是，最右侧为低位第0位，左侧为高位。1000位的二进制数，位序自右向左是0～999。

【成员函数】

• count()：统计有多少位是1。
• any()：若至少有一位是1，则返回true。
• none()：若没有位是1，全为0，则返回true。
• set()：将所有位置1。
• set(k)：将第k 位置1。
• set(k , val)：将第k 位的值改为val，即s [k]=val。
• reset()：将所有位置0。
• reset(k)：将第k 位置0，即s [k]=0。
• flip()：将所有位取反。
• flip(k)：将第k 位取反。
• size()：返回大小（位数）。
• to_ulong()：返回它转换为unsigned long的结果，如果超出范围，则报错。
• to_string()：返回它转换为string的结果。

【bitset 定义和初始化】

bitset 的构造函数

bitset<n> b;  //b有n位，每位都是0

bitset<n> b(u); //b是unsigned long型 u 的一个副本

bitset<n> b(s); //b 是string 对象s 中含有的位串的副本

bitset<n> b(s , pos , n); // b是 s 中从位置pos 开始的n 位副本
1
2
3
4
5
6
7

在定义bitset时，要明确bitset有多少位，必须在尖括号内给出它的长度值，给出的长度值必须是常量表达式。“bitset<32>bitvec;”表示定义bitvec为32位的bitset对象，bitvec的位序自右向左为0～31。

【用unsigned 类型的值初始化 bitset 对象】

当用unsigned long值作为bitset对象的初始值时，该值将转化为二进制的位模式，而bitset对象中的位集将作为这种位模式的副本。如果bitset类型的长度大于unsigned long值的二进制位数，则其余高阶位置为0；如果bitset类型的长度小于unsigned long值的二进制位数，则只使用unsigned值中的低阶位，超过bitset类型长度的高阶位将被丢弃。在32位unsigned long值的机器上，十六进制值0xffff表示为二进制位就是16个1和16个0（每个0xf都可被表示为1111）。

[举个栗子]

可以用0xffff初始化bitset对象：

bitset<16> bitvec1(0xffff);   //0-15 位置1

bitset<32> bitvec2(0xffff);   //0-15 位置1,16 - 31 位置0

bitset<128> bitvec3(0xffff);  //0-15 位置1,16 - 31 位置0，32 - 127 位置0
1
2
3
4
5

在上面的三个例子中，0～15位都置1。由于bitvec1的位数少于unsigned long值的位数，因此bitvec1的初始值的高阶位被丢弃。bitvec2和unsigned long值的长度相同，因此所有位正好被置为初始值。bitvec3的长度大于32，31位以上的高阶位就被置为0。

【用输出操作符 输出 bitset对象中的位模式】

0-15 位置1,16 - 31 位置0 【从右到左】

【用string 对象初始化 bitset 对象】

当用string对象初始化bitset对象时，string对象直接被表示为位模式。
从string对象读入位集的顺序是从右向左：

[举个栗子]

可以看到，在bitvec4的位模式中，第2、3位被置为1，其余位置都被置为0。如果string对象的字符个数小于bitset类型的长度，则高阶位将被置为0。

string对象和bitset对象之间是反向转化的：string对象的最右边字符（即下标最大的字符）用来初始化bitset对象的低阶位（即下标为0的位）。

【也可以用某个子串作为初始值】

bitvec5(str, 5, 4)表示从str[5]开始取4个字符初始化bitvec5。如果省略第3个参数，则表示取从开始位置一直到string末尾的所有字符。bitvec6(str, str.size() - 4)表示取出str末尾的4位来对bitvec6的低4位进行初始化。

【bitset 上的操作】

any/none。如果在bitset对象中有一个或多个二进制位被置为1，则any操作返回true，否则返回false；相反，如果bitset对象中的二进制位全为0，则none操作返回true。

[举个栗子]

count/size。可以使用count操作统计二进制位为1的个数：

[举个栗子]

count操作的返回类型是标准库中命名为size_t的类型。与vector和string中的size操作一样，bitset的size操作返回bitset对象中二进制位的个数，返回值的类型是size_t。

set/test。可以用下标操作符读或写某个索引位置的二进制位。

除了用下标操作符，还可以用set设置给定二进制位的值。

一样的效果。

为了测试某个二进制位是否为1，可以用test操作或者下标操作符。如果测试的二进制位为1，则返回true，否则返回false。

也可以直接 if(bitvec[i]) ，测试第i位是否为1，效果不变

set/reset。set和reset操作分别用来对整个bitset对象的所有二进制位都置1和都置0。

[举个栗子]

flip。flip操作可以对bitset对象的所有位或特定位按位取反。

to_ulong。to_ulong操作返回一个unsigned long值，该值与bitset对象的位模式存储值相同。仅当bitset类型的长度小于或等于unsigned long的长度时，才可以使用to_ulong操作。

[举个栗子]

to_ulong操作主要用于把bitset对象转到C风格或标准C++之前风格的程序上。如果bitset对象包含的二进制位数超过unsigned long值的长度，则将产生运行时异常。

to_string()。to_string操作主要用于把bitset对象转化为字符串。

将十进制数转化为二进制数。bitset可以很方便地将十进制数转化为二进制数。

[举个栗子]