目录

相关概念

位图的应用

bitset的使用

定义方式

bitset成员函数的使用

bitset中运算符的使用

bitset中的<<和>>运算符的使用

bitset中对应的关系运算符、赋值运算符、单目运算符、复合赋值运算符的相关使用

bitset中位运算符的使用

bitset中对于[ ]运算符的使用

---

相关概念

实际上我们的正常在写一些题目的时候是会用到位图的，尤其是关于大规模数据的题目的时候，但是一般我们并不会直接使用这里讲的bitset，一般的我们会自己模拟实现，但是这里的结构可以解决一些我们不太好快速实现的情况。

我们在讨论位图的问题的时候，免不了讨论一个关于大数据存在的问题：

假设我们这里有40亿个不重复的乱序的无符号整数，需要你判断一个数在不在这些数里面：
我们这个时候可能会想到的方法：

第一种：将这些数存起来，然后排序，最后二分查找。

第二种：使用哈希表，存储pair<int, bool>，判断存不存在。

但是我们要想将我们的这些数存到我们的内存中，需要至少16GB的空间，这里的空间消耗是非常大的，非常不合理。

这个时候我们就可以使用我们的位图来解决了：

这里位图实现的基本逻辑就是使用我们的一个一个的比特位来表示每一个数字的存在的状态（0/1），下面我们还是来举个栗子说明一下：

我们根据无符号整数的范围就可以知道我们的，我们需要2^32个比特位，也就是512MB的空间，这比我们的16GB要少得多。

位图的应用

1、大数据查找。

2、布隆过滤器。

3、集合的操作。

4、去重操作。

5、图算法中的优化。

下面有两个题，感兴趣的可以做一做：

bitset的使用

定义方式

第一种方式：直接构造默认的20位的位图，所有的位默认就是0。

bitset<20> bs; // 00000000000000000000

第二种方式：构造一个20位的位图，根据所给值初始化前面的位。

bitset<20> bs1(100); // 00000000000001100100 十进制
bitset<20> bs2(0123); // 00000000000001010011 八进制
bitset<20> bs3(0x3f); // 00000000000000111111 十六进制

第三种方式：构造以20位的位图，根据字符串表示的0和1来转换成位图里面的0和1。

bitset<20> bs(string("1010101")); // 00000000000001010101

bitset成员函数的使用

常见的成员函数如下：

成员函数	功能描述
bitset<N>::size()	返回 bitset 中的位数，即 N。
bitset<N>::count()	返回 bitset 中为 1 的位的个数。
bitset<N>::any()	如果 bitset 中有任何位为 1，则返回 true，否则返回 false。
bitset<N>::none()	如果 bitset 中所有位都是 0，则返回 true，否则返回 false。
bitset<N>::test(pos)	检查 bitset 中索引为 pos 的位是否为 1。如果为 1，返回 true，否则返回 false。
bitset<N>::set(pos)	将 bitset 中索引为 pos 的位设置为 1。
bitset<N>::set()	将所有位设置为 1。
bitset<N>::reset(pos)	将 bitset 中索引为 pos 的位设置为 0。
bitset<N>::reset()	将所有位设置为 0。
bitset<N>::flip(pos)	反转 bitset 中索引为 pos 的位的值（0 变 1，1 变 0）。
bitset<N>::flip()	反转 bitset 中所有位的值（0 变 1，1 变 0）。
bitset<N>::operator[]	通过下标访问 bitset 中指定位置的位（0 或 1）。
bitset<N>::to_string()	返回 bitset 的二进制字符串表示。
bitset<N>::to_ulong()	将 bitset 转换为 unsigned long 类型的数值（假设位数不超过 unsigned long 的位数）。
bitset<N>::to_ullong()	将 bitset 转换为 unsigned long long 类型的数值（假设位数不超过 unsigned long long 的位数）。

使用的示例：

#include <iostream>
#include <bitset>
using namespace std;
int main() {
    bitset<8> bs("10101010");
    // 返回 bitset 中的位数
    cout << bs.size() << endl;
    // 返回 bitset 中的1的个数
    cout << bs.count() << endl;
    // 如果 bitset 任何位有1就返回true，否则返回false
    cout << (bs.any() ? "Yes" : "No") << endl;
    // 如果 bitset 所有位都是0，就返回true，否则返回false
    cout << (bs.none() ? "Yes" : "No") << endl;
    // 检查我们的 bitset 中索引为pos的位是不是1
    cout << (bs.test(0) ? "Yes" : "No") << endl;
    cout << (bs.test(1) ? "Yes" : "No") << endl;
    // 将我们的 bitset 中的pos位的值设置为1
    bs.set(1);
    cout << bs << endl;
    // 将我们的 bitset 中的所有位设置为1
    bs.set();
    cout << bs << endl;
    // 将 bitset 中索引为 pos 的位设置为 0
    bs.reset(1);
    cout << bs << endl; 
    // 将所有位设置为 0
    bs.reset();
    cout << bs << endl;  
    // 反转 bitset 中索引为 pos 的位的值
    bs.flip(2);
    cout << bs << endl;  
    // 反转 bitset 中所有位的值
    bs.flip();
    cout << bs << endl;
    // 通过下标访问 bitset 中指定位置的位
    cout << bs[3] << endl;  
    // 返回 bitset 的二进制字符串表示
    cout <<  bs.to_string() << endl; 
    // 将 bitset 转换为 unsigned long 类型的数值
    cout << bs.to_ulong() << endl;  
    // 将 bitset 转换为 unsigned long long 类型的数值
    cout << bs.to_ullong() << endl;  
    return 0;
}

测试效果：

bitset中运算符的使用

🔖bitset中的<<和>>运算符的使用

我们的bitset容器对<<和>>运算符进行了重载操作，我们可以直接使用我们的<<和>>对bitset容器的对象进行输入和输出操作。

代码如下：

#include <bitset>
#include <iostream>
using namespace std;
int main() {
    bitset<20> bs;
    cin >> bs;
    cout << bs << endl;
    return 0;
}

测试效果如下：

🔖bitset中对应的关系运算符、赋值运算符、单目运算符、复合赋值运算符的相关使用

我们这里的运算符包括了如下几个：

关系运算符：==，!=

赋值运算符：=

单目运算符：~

复合赋值运算符：&=、|=、^=、<<=、>>=

示例代码如下：

#include <iostream>
#include <bitset>
using namespace std;
int main() {
    bitset<20> bs1, bs2;
    cin >> bs1;
    cin >> bs2;
    bs1 >>= 1;
    cout << bs1 << endl;
    bs2 |= bs1;
    cout << bs2 << endl;
    return 0;
}

测试效果如下：

🔖bitset中位运算符的使用

我们的bitset容器可以对于我们的每一位进行位的逻辑处理。

代码如下：

#include <iostream>
#include <bitset>
using namespace std;
int main() {
    bitset<20> bs1, bs2;
    cin >> bs1 >> bs2;
    cout << (bs1 & bs2) << endl;
    cout << (bs1 | bs2) << endl;
    cout << (bs1 ^ bs2) << endl;
    return 0;
}

测试效果如下：

🔖bitset中对于[ ]运算符的使用

我们可以像使用数组中的[ ]对bitset容器的指定位上的数据进行访问和修改操作。

代码如下：

#include <iostream>
#include <bitset>
using namespace std;
int main() {
    bitset<20> bs;
    cin >> bs;
    cout << bs[0] << endl;
    bs[0] = 1;
    cout << bs << endl;
    return 0;
}

测试效果如下：