下载掌阅APP，畅读海量书库
立即打开
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的结果。
下面列出了bitset的构造函数：
在定义bitset时，要明确bitset有多少位，必须在尖括号内给出它的长度值，给出的长度值必须是常量表达式。“bitset<32> bitvec;”表示定义bitvec为32位的bitset对象，bitvec的位序自右向左为0～31。
当用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对象中的位模式：
输出结果如下：
当用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位进行初始化。
（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：
每个元素都可以用一个二进制数记录所属的集合。最右侧为低位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”。
