购买
下载掌阅APP,畅读海量书库
立即打开
畅读海量书库
扫码下载掌阅APP

2.4.7 bitset

bitset是一个多位二进制数,如同状态压缩的二进制数。使用bitset时,需要引入头文件#include<bitset>。“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的结果。

1)bitset定义和初始化

下面列出了bitset的构造函数:

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

2)用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对象:

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

可以用输出操作符输出bitset对象中的位模式:

输出结果如下:

3)用string对象初始化bitset对象

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

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

注意: string对象和bitset对象之间是反向转化的:string对象的最右边字符(即下标最大的字符)用来初始化bitset对象的低阶位(即下标为0的位)。当用string对象初始化bitset对象时,记住这一差别很重要。

也可以只用某个子串作为初始值:

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

4)bitset上的操作

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

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

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

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

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

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

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

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

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

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

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

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

训练 集合运算

题目描述(POJ2443): 给定 N 个集合,第 i 个集合S i 有C i 个元素(集合可以包含两个相同的元素)。集合中的每个元素都用1~10 000的正数表示。查询两个给定元素 i j 是否同时属于至少一个集合。换句话说,确定是否存在一个数字 k (1≤ k N ),使得元素 i 和元素 j 都属于S k

输入: 输入的第1行包含一个整数 N (1≤ N ≤1000),表示集合的数量。第2~ N +1行,每行都以数字C i (1≤C i ≤10 000)开始,后面有C i 个数字,表示该集合中的元素。第 N +2行包含一个数字 Q (1≤ Q ≤200 000),表示查询数。接下来的 Q 行,每行都包含一对数字 i j (1≤ i , j ≤10 000, i 可以等于 j ),表示待查询的元素。

输出: 对于每个查询,如果存在这样的数字 k ,则输出“Yes”,否则输出“No”。

1. 算法设计

本题查询两个元素是否同属于一个集合(至少一个)。所属集合可以用二进制表示法。

输入样例1:

每个元素都可以用一个二进制数记录所属的集合。最右侧为低位0位,自右向左。例如,1属于第1个集合,就将1对应的二进制数的第1位置为1,即 s [1]=0010;1还属于第2个集合,就将1对应的二进制数的第2位置为1,即 s [1]=0110; s [1]=0110表示元素1属于1、2两个集合。同理, s [2]=0110, s [3]=0010, s [5]=0100, s [10]=1000。

可以采用bitset解决。

(1)定义一个bitset数组,对每个数都用二进制表示。

(2)根据输入数据,将元素所属集合对应的位置为1。

(3)根据查询输入的两个数 x y ,统计 s [ x ]& s [ y ]运算后二进制数中1的个数,如果大于或等于1,则输出“Yes”,否则输出“No”。 sdN5zRMdDzGIh+zzRAehdRH1vxLoRBYBsFRn+VcOH/ZxZwiUwo4nb6BU0xFAS3hC

2. 算法实现
点击中间区域
呼出菜单
上一章
目录
下一章
×