关于bitset

konyakest · 2022-07-12 10:28:17 · 个人记录

bitset作为C++一个非常好用的STL（虽然官方说它不是STL，但是我们暂且不纠结），在一些题目中巧妙地使用会产生非常不错的效果。

一、深入了解

bitset<N> b;

相当于

bool b[N];

注意：此处“相当于”指bitset储存N为bool值，并且可以访问下标

例如：

bitset<1005> b;
b[1]=1;
b[3]=1;
for(int i=1;i<=3;i++) cout<<b[i];
//输出101

bitset的好处（vs bool数组）：

省空间（最多相当于原bool数组内存的\frac{1}{6}）

例如：link -> link

单纯把bool数组对声明改为bitset，总内存从110.86MB->16.55MB

对于整体操作，可以优化至O(\frac{n}{w})，w约为5~10

例如：

复杂度	范围（1 秒，允许任意优化开关）
O(\frac{n^2}{w})	2\times 10^4\sim 10^5
O(n^2)	5\times 10^3\sim 10^4
O(\frac{n^3}{w})	2\times 10^3
O(n^3)	500

坏处：

没有整体操作时，不开O(2)可能会不如bool数组快

二、非优化函数

1. 定义与构造函数

bitset<N> b;//默认全部为0
bitset<N> b("10101");//将b赋值为二进制数10101
bitset<N> b(3);//将b赋值为3的二进制数

例：

// The default is that N is 8.
std::bitset<N> s (std::string("00110101"));

需要注意的是集合内部的下标是从右向左单调递增的，即字符串的第一位代表set的第7位(从0编号)。上面的赋值方法对应s的值如下表：

将它理解为二进制数的个位、10位、100位即可

2. 数组下标访问

3. cin、cout

std::cin >> s;                          // 1101
std::cout << s << std::endl;            // 000001101

4. 转换函数

bitset提供两个转换函数，可以转换为std::string型，unsigned long int型（即unsigned int）。函数名为别为to_string()和to_ulong();

在C++11标准下可以转换为unsigned long long int型，函数名为to_ullong()

其中转换成std::string型会转换成01串，其他两个类型会按照二进制位转换成十进制数字。

// The default is that N is 8.
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

三、优化函数

1. 位运算

以下函数：

<<、 >>、 | 、&、 ^

注意：bitset不支持加减乘除

2. any、none

判断bitset是否为0

3. count

返回bitset中1的个数

4. _Find_first、_Find_next

很有趣但是没怎么有用的两个函数。

_Find_fisrt就是找到从低位到高位第一个1的位置

#include<bits/stdc++.h>
int main() {
    std::bitset<1001> B;
    B.set(2); B.set(4); B.set(233);
    std::cout << B._Find_first();
}

输出结果为2

_Find_next就是找到当前位置的下一个1的位置

#include<bits/stdc++.h>
int main() {
    std::bitset<1001> B;
    B.set(2); B.set(4); B.set(233);
    std::cout << B._Find_next(5);
}

输出结果为233 1001，也就是说如果某个元素之后没有元素的话会返回bitset的大小

那么我们可以这样去遍历一个bitset

#include<bits/stdc++.h>
int main() {
    std::bitset<1001> B;
    B.set(2); B.set(4); B.set(233);
    for(int i = B._Find_first(); i != B.size(); i = B._Find_next(i)) 
        std::cout << i << ' ';
}

输出结果为2 4 233。

这样遍历的复杂度是O(n/w)的

如果我们想要找到bitset的最高位，我们可以手写一个函数

template <unsigned N>
int find_first(bitset<N> b){
    int i;
    for(i=b._Find_first();b._Find_next(i)!=b.size();i=b._Find_next(i));
    return i;
}

四、特殊用法

例如：枚举所有8选5的情况

for(int i=0; i<=((1<<8)-1); i++) {
    bitset<10> B(i);
    if(B.count()==5) ans++;
}