给40亿个不重复的无符号整数，没排过序。给一个无符号整数，如何快速判断一个数是否在这40亿个数中？
要判断一个数是否在某一堆数中，我们可能会想到如下方法：
单从方法上来看，这两种方法都是可以，而且效率也不错，第一种方法的时间复杂度是O(N*logN)，第二种方法的时间复杂度是O(N)。
但问题是这里有40亿个数，若是我们要将这些数全部加载到内存当中，那么将会占用16G的空间，空间消耗是很大的。因此从空间消耗来看，上面这两种方法实际都是不可行的。
位图解决
无符号整数总共有232个，因此记录这些数字就需要232个比特位，也就是512M的内存空间，内存消耗大大减少。
所谓位图，就是用每一位来存放某种状态，适用于海量数据，数据无重复的场景。通常是用来判断某个数据存不存在的。
常见位图的应用如下：
方式一： 构造一个16位的位图，所有位都初始化为0。
方式二： 构造一个16位的位图，根据所给值初始化位图的前n位。
方式三： 构造一个16位的位图，根据字符串中的0/1序列初始化位图的前n位。
bitset中常用的成员函数如下：
使用示例：
版权声明：
本文来源网络，所有图片文章版权属于原作者，如有侵权，联系删除。
本文网址：https://www.mushiming.com/mjsbk/2074.html