提示：文章写完后，目录可以自动生成，如何生成可参考右边的帮助文档

前言

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

这是一个面试题，我们要查找一个数，若是用map存，则要开很大的空间进行存储，很消耗内存。

且时间效率很低，所以我们用位图进行存放数据看数据是否存在

一、位图的概念

位图本质是直接定址法，存储数据用vector，体现数据是否存在用0/1；所以使用位图可以节省空间，下面对位图的成员函数进行分析；

二、位图的成员函数

1.set函数

void set(size_t x)
{
            size_t i = x / 32;//第几个位置，这个数存在于该数组下标之中
			size_t j = x % 32;//偏移量

			_bs[i] |= (1 << j);
}

这是存在置1的函数，

开一个这样的空间，这里使用32位，刚好是一个int，将x进行处理，然后和这个表进行位运算，是1则说明存在，是0则不存在，这时我们就可以通过test检查是否存在了

2.reset函数

void reset(size_t x)
		{
			size_t i = x / 32;
			size_t j = x % 32;

			_bs[i] &= ~(1 << j);//取反置0

		}

对位图进行取反置0；这样就可以将存在的数据变为不存在，这里主要是位运算

3.test函数

bool test(size_t x)
		{
			size_t i = x / 32;
			size_t j = x % 32;

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

检查是否存在，存在返回1，不存在返回0即可

总结

位图的优点是用少空间可以找多数据，对海量数据的存储寻找有作用

缺点：只能对整形数据进行存储，而生活中的数据不止这些，所以要用别的容器进行探查，引出布隆过滤器，看下文