【STL】bitset位图的介绍和使用

位图的介绍和使用"/>

【STL】bitset位图的介绍和使用

⭐博客主页：️CS semi主页
⭐欢迎关注：点赞收藏+留言
⭐系列专栏：C++进阶
⭐代码仓库：C++进阶
家人们更新不易，你们的点赞和关注对我而言十分重要，友友们麻烦多多点赞＋关注，你们的支持是我创作最大的动力，欢迎友友们私信提问，家人们不要忘记点赞收藏＋关注哦！！！

bitset位图的介绍和使用

• 一、bitset的介绍
• • 1、引例
  • 2、位图的概念
  • 3、位图的应用
• 二、bitset的使用
• • 1、bitset的使用
  • 2、bitset运算符的使用
  • • （1）bitset中>>、<<运算符的使用
    • （2）bitset中赋值运算符、关系运算符、复合赋值运算符、单目运算符的使用
    • （3）bitset中位运算符的使用
    • （4）bitset中[ ]运算符的使用

一、bitset的介绍

1、引例

给40亿个不重复的无符号整数，没排过序。给一个无符号整数，如何快速判断一个数是否在这40亿个数中？

我们有以下两种方法：
1、先进行遍历排序，然后通过二分法查找需要找的元素是否在这个堆中。
2、将这组数插入到unordered_set中，通过调用find函数来查找当前的元素是否在这个堆中。

我们看一下这两种方法的时间复杂度：第一个为O(N*logN)，第二个为O(N)；但最大的问题是，我们有40亿个数，全部加载到内存中有16G的存储空间，空间消耗很大，所以我们用位图来解决：

无符号整数总共有232个，因此记录这些数字就需要232个比特位，也就是512M的内存空间，内存空间完美解决。

2、位图的概念

位图，就是用每一位来存放某种状态，适用于海量数据，数据无重复的场景。通常是用来判断某个数据存不存在的。

3、位图的应用

快速查找某个数据是否在一个集合中。
排序。
求两个集合的交集、并集等。
操作系统中磁盘块标记。

二、bitset的使用

1、bitset的使用

若set、reset和flip三个成员函数未指定指定位进行改变的话，那么就是更改所有位。

#include <iostream>
#include <bitset>
using namespace std;int main()
{bitset<8> bs;bs.set(3); //设置第3位bs.set(4); //设置第4位cout << bs << endl; //00011000bs.flip(); //反转所有位cout << bs << endl; //11100111// 计算位图里面的1的个数cout << bs.count() << endl; //6// 获取指定位的状态cout << bs.test(2) << endl; //1bs.reset(0); //清空第0位cout << bs << endl; //11100110bs.flip(7); //反转第7位cout << bs << endl; //01100110// 计算位图里面的1和0的总个数cout << bs.size() << endl; //8cout << bs.any() << endl; //1bs.reset(); //清空所有位cout << bs.none() << endl; //1bs.set(); //设置所有位cout << bs.all() << endl; //1return 0;
}

2、bitset运算符的使用

（1）bitset中>>、<<运算符的使用

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

（2）bitset中赋值运算符、关系运算符、复合赋值运算符、单目运算符的使用

赋值运算符：=
关系运算符：==、!=
复合赋值运算符：&=、|=、^=、<<=、>>=
单目运算符：~

#include<iostream>
#include<string>
#include<bitset>
using namespace std;int main()
{bitset<8> bs1(string("10101010"));bitset<8> bs2(string("10101010"));bs1 >>= 1;cout << bs1 << endl; // 01010101bs2 |= bs1;cout << bs2 << endl; // 11111111return 0;
}

（3）bitset中位运算符的使用

&、|、^三个运算符

#include<iostream>
#include<string>
using namespace std;#include<bitset>int main()
{bitset<8> bs1(string("10101010"));bitset<8> bs2(string("01010101"));cout << (bs1 & bs2) << endl; // 00000000cout << (bs1 | bs2) << endl; // 11111111cout << (bs1 ^ bs2) << endl; // 11111111return 0;
}

（4）bitset中[ ]运算符的使用

#include<iostream>
#include<string>
using namespace std;#include<bitset>int main()
{bitset<8> bs1(string("10101010"));cout << bs1[0] << endl; // 0bs1[0] = 1;cout << bs1 << endl; // 10101011return 0;
}