1. 位图
腾讯面试题：给40亿个不重复的无符号整数，没排过序。给一个无符号整数，
如何快速判断一个数是否在这40亿个数中。
根据我们现有的知识，该如何处理上面的问题呢？
1. 遍历，时间复杂度O(N)
2. 排序(O(NlogN))，利用二分查找: logN
3. 红黑树 / 哈希表。
还有很多其他的方式，但是这些方式都行不通，
先来口算一下40亿的无符号整数占用多大的内存空间：
1024字节 = 1KB
1024KB = 1MB
1024MB = 1GB
10 0000 0000（九个零 -> 10亿）
10亿个字节 ≈ 1GB。
40亿个字节 ≈ 4GB。
40亿个无符号整数 ≈ 16GB。
而一般的内存根本放不下这么多的数据，无论是上面的哪种方法，都需要存放数据本身，即使是用数组来存放都需要16GB，如果用红黑树(有三叉链，颜色)需要大的内存，哈希表虽然少一点，但是仍然有next指针，还是存放不下。
问题中只要求判断一个数是否在这40亿个数据中，所以可以不存放数据本。
可以采用下面的位图的方式来处理这个问题。
1.1 位图的概念
位图：就是用每一比特位来存放某种状态，适用于海量数据，数据无重复的场景。
通常是用来判断某个数据存不存在的。1字节 = 8 bit。
位图就是哈希结构，这里我们用直接定址法，1表示在，0表示不在，就能很好处理这个面试题。对于40亿个数据，至少需要40亿个比特位才能标识它们的状态。
对于这种情况一般选择2^32个比特位：2^32 = 42亿9千多万，40亿个数据完全可以表示的下，此时相当于一个数组，有2^32个元素，每个元素是一个比特位。
使用位图方式占用的内存就小多了：
1个字节等于8个比特位，8 = 2^3，1024 = 2^10。
- 2^32个比特位 = 2^29个字节 = 2^19KB = 2^9MB = 512MB = 0.5GB
- 从最开始需要16GB内存空间直接下降到了需要0.5GB的空间。
但是在语言层面上并没有比特位的数组。
- 2^32个比特位可以用2^27个int类型的数组来表示。
- 也可以用2^29个char类型的数组来表示。
随便例举一些数字，如上图所示，这里采用char类型为数组的基本单位。
数据范围是1到22，所以需要3个char类型的变量。
下标为1的比特位表示数字1的存在情况，下标为18的比特位表示数字18是否存在。
上图中，存在3个char类的变量，一共24个比特位，整体标号的话是0~23。
0~7使用第一个char类型的变量。
8~15使用第二个char类型变量。
16~23使用第三个char类型变量。
这3个char类型的变量是用一个数组实现的，即char [3]。
这3个char类型变量的地址从左到右依次升高。
每个char类型中比特位却是：低的比特位在右，高的比特位在左。
这是由我们的使用习惯决定的，比如3用二进制表示就是11，6用二进制表示就是100，
低比特位在右，高比特位在左。
不使用int类型数组的原因：（用int也可以）
我们知道，数据在内存中的存储是有大小端的，如果使用int类型的数组，上图就变成：
一个int就是4个字节，8个比特位只需要一个int类型的数据就够了，并且还多出8个比特位。假设上图中是小端存储方式，并且是处理完的位图，此时将这份代码换到了大端存储方式的机器上：
此时位图结构就变成了下图中所示，原本表示数字0~7的8个比特位放在了高地址处，变成了表示24 ~31的8个比特位。
原本在小端机上的程序在大端机上极有可能出现BUG。而采用char类型数组就不用考虑大小端的问题，因为一个char类型就是一个字节，每个char都是从低地址到高地址排列。
上面是在内存中存储的真实样子，我们在使用的时候无需知道位图在内存中样子。这种方式就是一种哈希思想，将数据直接映射到位图上。
如何确定一个数据映射在位图的哪个比特位呢？以整数18为例说明：
8映射在位图的下标为2的八个比特位中的某一个，也就是第三个char类型变量。具体映射在下标为2的char类型变量中下标为2的比特位上，也就是在这个char类型中第三个比特位上。
确定映射到char类型变量的下标：18 / 8 = 2。
确定映射到比特位的下标：18 % 8 = 2。
可以根据上面的图确定一下，发现和我们算出来的结果是一样的。求其他数据的映射位置时，只需要将18换成对应数据即可。
1.2 位图的实现
BitSet.h：
#pragma once #include <iostream> #include <vector> using namespace std; namespace rtx { template<size_t N> class bitset //构造函数开空间，只需开N / 8 + 1 { public: bitset() { //_bits.resize(N / 8 + 1, 0); _bits.resize((N >> 3) + 1, 0); // 即上面注释的，效率快一点点 } protected: vector<char> _bits; }; }
使用非类型模板参数，该参数用来指定位图比特位的个数。
底层使用的是vector，vector中存char类型变量。
在构造函数中需要指定vector的大小，否则vector的大小是0，一个比特位也没有。
非类型模板参数N指定是比特位的个数，而构造函数开辟的是char类型变量的个数，所以需要N / 8。
由于N / 8的结果不是整数时会取整而抛弃小数部分，所以需要在N /8 后再加1，也就是再增加 8 个比特位来确保位图够用。
CPU在计算除法的时候，其实是很复杂的，而进行移位运算就很简单。N / 8相当于N右移3位。所以我们使用移位运算来代替除法来提高效率，需要注意的是，加法的优先级比移位运算高，所以必须给(N>>3)加括号，否则就是成了 N>>4了。
下面来写bitset的接口函数：
set(); 该接口的作用是将x映射在位图中的比特位置1，表示该数据存在。
- 首先将x映射在位图中的位置计算出来。
- 然后将映射的比特位置1。
怎么将对应的比特位置1？这就要我们以前C语言学的知识：
如上图所示，要将一个char类型中的8个比特位的某一个位置一而不影响其他位，就需要或等一个只有那个位是1其他位都是0的char类型，这样一个char类型可以通过1左移固定位数得到。
void set(size_t x) { size_t i = x >> 3; // 将x映射在位图中的位置计算出来。 size_t j = x % 8; // //映射到char中第几个比特位 _bits[i] |= (1 << j); //将映射的比特位置1。 }
现在来实现reset()；该接口的作用是将x映射在位图中的比特位置0，表示该数据不存在。
和set的思路一样同样先计算处x所在位图中的位置。 然后再进行置0。
怎么将对应比特位置0？上面是或等，这里就要与等一个数。
这里与等一个只有那个位是0其他位都是1的char类型变量，这样一个char类型可以通过1左移固定位数（就是set或等的那个数），然后按位取反得到。
void reset(size_t x) { size_t i = x >> 3; // 将x映射在位图中的位置计算出来。 size_t j = x % 8; // //映射到char中第几个比特位 _bits[i] &= ~(1 << j); //将映射的比特位置0，这里~是按位取反，不要用到!逻辑取反 }
现在来实现test(); 该接口的作用是在位图中查找数据x是否存在。
- 首先计算出x映射在位图中的位置。
- 然后看该比特位是0还是1。
如上图所示，判断某个比特位是1还是0，需要与一个只有这个位是1其他位都是0的char类型变量，如果这个bit是0，那么与以后的结果就是0，对应的bool值flase，如果这个bit是1，那么与以后的结果就不是0，对应的bool值是true。
bool值本质上是4个字节的整形，所以这里涉及到了整形提升，但是并没有影响。
如果与以后的结果是0，整形提升后的结果仍然是0，bool值就是false。
如果与以后的结果非0，即使符号位是1，整形提升和的结果仍然非0，bool的值就是true。
bool test(size_t x) { size_t i = x >> 3; // 将x映射在位图中的位置计算出来。 size_t j = x % 8; // //映射到char中第几个比特位 return _bits[i] & (1 << j); //与上除了对应比特位是1，其它位都是0的数，得到对应比特位bool值 }
位图主要的接口就是这三个，下面来测试一下：
#include "BitSet.h" void test_bitset() { rtx::bitset<100> bs; //上面面试题开范围可以这样开：bitset<-1> bs1; bs.set(8); bs.set(9); bs.set(20); cout << bs.test(8) << endl; cout << bs.test(9) << endl; cout << bs.test(20) << endl; cout << bs.test(30) << endl << endl; bs.reset(8); bs.reset(20); cout << bs.test(8) << endl; cout << bs.test(9) << endl; cout << bs.test(20) << endl; } int main() { test_bitset(); return 0; }
STL中的位图：
在STL库中，是存在位图的，但是用的比较少。
上面实现的这3个操作也是有的，当然它还提供了其他的接口，这里就不介绍了。
从C语言到C++_32(哈希的应用)位图bitset+布隆过滤器+哈希切割（中)：https://developer.aliyun.com/article/1522346
