目录

一、bitset的基本介绍

1. 位图的概念

2. 位图的应用

二、biset的基本使用

1. bitset的成员函数

2. 基本使用介绍

1. 定义方式

2. 成员函数的使用

一、bitset的基本介绍

1. 位图的概念

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

例如下面的场景：

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

1. 
   
   遍历的方式，时间复杂度为O(N)；
   
   
2. 
   
   先将其排序（O(N*logN)），利用二分查找（logN）；
   
   
3. 
   
   位图解决
   
   

前两种方法思路上是没有问题的，但是这里有40亿个数，若是我们要将这些数全部加载到内存当中，那么将会占用16G（




40亿个整数，每个整数占4字节，那么就是160亿字节，1G = 1024*1024*1024；大约是10亿字节，所以算下来是16G




）的空间，空间消耗是很大的。因此从空间消耗来看，上面这两种方法实际都是不可行的。

位图是如何解决的呢？

数据是否在给定的整形数据中，结果是在或者不在，刚好是




两种状态




，那么可以使用一个二进制比特位来代表数据是否存在的信息，如果二进制比特位为1，代表存在，为0代表不存在。比如：

无符号整数总共有2^32个，因此记录这些数字就需要2^32个比特位，也就是512M的内存空间，内存消耗大大减少。

2. 位图的应用

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

二、biset的基本使用

1. bitset的成员函数

2. 基本使用介绍

1. 定义方式

#include <iostream>
#include <bitset>
#include <string>
using namespace std;

int main()
{
	//构造一个16位的位图，所有位都初始化为0 
	bitset<16> bst1; //0000 0000 0000 0000

	//构造一个16位的位图,根据所给定的值初始化位图
	bitset<16> bst2(0xfa2); //0000 1111 1010 0010

	//构造一个16位的位图,通过字符串中的0/1初始化位图
	bitset<16> bst3(string("0101111001")); //0000000101111001

	return 0;
}

2. 成员函数的使用

#include <iostream>
#include <bitset>
#include <string>
using namespace std;

int main()
{
	//构造一个16位的位图，所有位都初始化为0 
	bitset<16> bst1; //0000 0000 0000 0000
	bst1.set(0); //将bst1位图中的第0位设置为1
	bst1.set(2); //将bst1位图中的第2位设置为1
	bst1.set(4); //将bst1位图中的第4位设置为1
	bst1.set(6); //将bst1位图中的第6位设置为1
	cout << bst1 << endl; // 结果0000000001010101

	cout << bst1.size() << endl; //获取bst1位图有多少个位可以被设置，结果：16

	cout << bst1.count() << endl;//获取多少个位被设置了，结果：4

	cout << bst1.test(1) << " " << bst1.test(2) << endl;//获取第1位和第2位的状态，结果：0 1

	cout << bst1.any() << endl;  //如果bst1位图中有任何一个位被设置了，返回true，结果：1
	cout << bst1.none() << endl; //如果bst1位图中没有位被设置了，返回true，否则返回false，结果：0
	cout << bst1.all() << endl;  //如果bst1位图中所有位被设置了，返回true，否则返回false，结果：0

	cout << bst1.reset(2) << endl;//清空第2位
	cout << bst1.reset() << endl; //清空所有位

	/********bitset容器中对[ ]运算符进行了重载，我们可以直接使用[ ]对指定位进行访问或修改*******/
	bitset<16> bst2(0x0);
	cout << bst2 << endl;
	bst2[0] = 1;
	bst2[2] = 1;
	bst2[4] = 1;
	bst2[6] = 1;
	/************还有其他的运算符重载，简单试一试就可以了************/
	return 0;
}