简介

std::bitset标准库中的一个存储0/1的大小不可变容器。严格来讲,它并不属于 STL。

由于内存地址是按字节即byte寻址,而非比特bit,一个bool类型的变量,虽然只能表示0/1, 但是也占了1 byte的内存。

bitset就是通过固定的优化,使得一个字节的八个比特能分别储存 8 位的0/1

对于一个 4 字节的 int 变量,在只存0/1的意义下,bitset占用空间只是其132\frac{1}{32},计算一些信息时,所需时间也是其132\frac{1}{32}

在某些情况下通过bitset可以优化程序的运行效率。至于其优化的是复杂度还是常数,要看计算复杂度的角度。一般bitset的复杂度记为:(设原复杂度为O(n)O(n)

  • O(nw)O(\frac{n}{w}),其中w=32w=32,这种记法较为普遍接受
  • O(nlogw)O(\frac{n}{logw}),其中wvwv为计算机一个整型变量的大小

构造函数

用字符串构造时,字符串只能包含 ‘0’ 或 ‘1’ ,否则会抛出异常。

构造时,需在<>中表明 bitset 的大小(即size)。

定义完bitset之后,可以用[]访问元素,注意最低为下标为0,也可以通过这种方式对某一位元素赋值也是可以的。这里可以等价于数组

在进行有参构造时,若参数的二进制表示比bitset的size小,则在前面用0补充;若比bitsize大,参数为整数时取后面部分,参数为字符串时取前面部分

注意
bitset用字符串构造时,可以看作是用倒着写的二进制数字进行构造

1
2
3
4
5
bitset<4> foo ("1011");

cout << foo[0] << endl;  //1
cout << foo[1] << endl;  //1
cout << foo[2] << endl;  //0

再看下面的两个栗子:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
bitset<4> bitset1;  //无参构造,长度为4,默认每一位为0

bitset<8> bitset2(12);  //长度为8,二进制保存,前面用0补充

string s = "100101";
bitset<10> bitset3(s);  //长度为10,前面用0补充

char s2[] = "10101";
bitset<13> bitset4(s2);  //长度为13,前面用0补充

cout << bitset1 << endl;  //0000
cout << bitset2 << endl;  //00001100
cout << bitset3 << endl;  //0000100101
cout << bitset4 << endl;  //0000000010101
1
2
3
4
5
6
7
8
9
10
11
bitset<2> bitset1(12);  //12的二进制为1100(长度为4),但bitset1的size=2,只取后面部分,即00

string s = "100101";  
bitset<4> bitset2(s);  //s的size=6,而bitset的size=4,只取前面部分,即1001

char s2[] = "11101";
bitset<4> bitset3(s2);  //与bitset2同理,只取前面部分,即1110

cout << bitset1 << endl;  //00
cout << bitset2 << endl;  //1001
cout << bitset3 << endl;  //1110
1
2
3
4
5
bitset<4> foo ("1011");

cout << foo[0] << endl;  //1
cout << foo[1] << endl;  //1
cout << foo[2] << endl;  //0

bitset的位运算

注意式子中有两个及以上bitset时,各bitset的长度相等才能进行运算,不然会报错

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
bitset<4> foo (string("1001"));
bitset<4> bar (string("0011"));

cout << (foo^=bar) << endl; // 1010 (foo对bar按位异或后赋值给foo)
cout << (foo&=bar) << endl; // 0010 (按位与后赋值给foo)
cout << (foo|=bar) << endl; // 0011 (按位或后赋值给foo)

cout << (foo<<=2) << endl; // 1100 (左移2位,低位补0,有自身赋值)
cout << (foo>>=1) << endl; // 0110 (右移1位,高位补0,有自身赋值)

cout << (~bar) << endl; // 1100 (按位取反)
cout << (bar<<1) << endl; // 0110 (左移,不赋值)
cout << (bar>>1) << endl; // 0001 (右移,不赋值)

cout << (foo==bar) << endl; // false (0110==0011为false)
cout << (foo!=bar) << endl; // true (0110!=0011为true)

cout << (foo&bar) << endl; // 0010 (按位与,不赋值)
cout << (foo|bar) << endl; // 0111 (按位或,不赋值)
cout << (foo^bar) << endl; // 0101 (按位异或,不赋值)

可用函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
bitset<8> foo ("10011011");

cout << foo.count() << endl;  //5  (count函数用来求bitset中1的位数,foo中共有5个1
cout << foo.size() << endl;   //8  (size函数用来求bitset的大小,一共有8位

cout << foo.test(0) << endl;  //true  (test函数用来查下标处的元素是0还是1,并返回false或true,此处foo[0]为1,返回true
cout << foo.test(2) << endl;  //false  (同理,foo[2]为0,返回false

cout << foo.any() << endl;  //true  (any函数检查bitset中是否有1
cout << foo.none() << endl;  //false  (none函数检查bitset中是否没有1
cout << foo.all() << endl;  //false  (all函数检查bitset中是全部为1

bitset<8> foo ("10011011");

cout << foo.flip(2) << endl;  //10011111  (flip函数传参数时,用于将参数位取反,本行代码将foo下标2处"反转",即0变1,1变0
cout << foo.flip() << endl;   //01100000  (flip函数不指定参数时,将bitset每一位全部取反

cout << foo.set() << endl;    //11111111  (set函数不指定参数时,将bitset的每一位全部置为1

cout << foo.set(3,0) << endl;  //11110111  (set函数指定两位参数时,将第一参数位的元素置为第二参数的值,本行对foo的操作相当于foo[3]=0
cout << foo.set(3) << endl;   //11111111  (set函数只有一个参数时,将参数下标处置为1

cout << foo.reset(4) << endl;  //11101111  (reset函数传一个参数时将参数下标处置为0
cout << foo.reset() << endl;   //00000000  (reset函数不传参数时将bitset的每一位全部置为0

小记

bitset的主要用途:将某些真或假的状态以bitset的形式存储,然后在状态转移时,可以相较于普通的循环降低较大常数的复杂度(通常为64或者32)

  • 例题
    「LibreOJ β Round #2」贪心只能过样例
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    #include <iostream>
    #include <cstdio>
    #include <algorithm>
    #include <cstring>
    #include <bitset>
    using namespace std;
    bitset<1000005> ans[101];
    int main()
    {
    int n, l, r;
    scanf("%d", &n);
    ans[0] = 1;
    for(int i = 1; i <= n; i++)
    {
    scanf("%d%d", &l, &r);
    for(int j = l; j <= r; j++)
    {
    ans[i] |= (ans[i-1] << (j*j)); //在前面的所有状态,每个数都+j*j,也就是所有1左移j*j的位置
    }
    }
    printf("%d\n", ans[n].count());
    return 0;
    }