bitset（位图）

位图的引入

我们用一道面试题来引入位图

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

我们会想到一下几种方法：

1. 遍历一遍，时间复杂度为O(N);
2. 排序 + 二分查找， 时间复杂度为O(NlogN);
   但是现在又出现了新的问题
   有40亿的数，
   一个整数占4四节,
   总共大约占16个G的内存空间
   空间消耗巨大
   除此之外，二分查找的话你数组还得是连续的。

所以，引出了位图来解决该问题

在上述问题中，一个数在与不在就只有两种情况，所以我们使用一个比特位来表示数是否存在，比特位为1则存在，为0则不存在；

所以究竟什么是位图呢？？？

位图的概念

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

位图的模拟实现

库中的位图，其中N代表位图的大小

位图最主要的三个接口

• set：将数据放入位图中
• reset：将数据从位图中删掉
• test：检测一个数据在不在位图中

在写set,reset等函数时，我们要知道
那就是 int 类型的数组一个元素有32个比特位
所以我们需要确定两个位置
一是数据在哪一个 int 中
二是数据在该 int 的第几个比特位
我们看下面的图理解一下

位图的基本框架

template<size_t N> // N是所有数中的最大值
class bit_set
{
public:
	bit_set()
	{
		_bits.resize(N / 32 + 1, 0);
	}
	void set(size_t x) // 将第x位变成1
	{}
	void reset(size_t x) // 将第x位由1变0
	{}
	bool test(size_t x)
	{}
private:
	vector<int> _bits;
};

set函数用于设置该位置

• 计算出该位位于第 i 个整数的第 j 个比特位
• 将1左移 j 位后与第 i 个整数进行或运算即可

// 设置位
void set(size_t x)
{
	// pos映射在第i个整数的第j位
	int i = x/ 32;
	int j = x% 32;
	_bits[i] |= (1 << j); // 将该位设置为1
}

reset函数用于清空该位置

• 计算出该位位于第 i 个整数的第 j 个比特位
• 将1左移 j 位再整体反转后与第 i 个整数进行与运算

// 清空位
void reset(size_t x)
{
	// pos映射在第i个整数的第j位
	int i = x/ 32;
	int j = x% 32;
	_bits[i] &= (~(1 << j)); // 将该位设置为0
}

test函数用于获取该位置的状态

• 计算出该位位于第 i 个整数的第 j 个比特位
• 将1左移 j 位后与第 i 个整数进行与运算得出结果
• 若结果非0，则该位被设置；若结果是1，则该位未被设置

bool test(size_t x)
{
	// pos映射在第i个整数的第j位
	size_t i = x / 32;
	size_t j = x % 32;

	return _bits[i] & (1 << j);
}