位图
给40亿个不重复的无符号整数，没排过序。给一个无符号整数，如何快速判断一个数是否在这40亿个数
中。【腾讯】
- 遍历，时间复杂度O(N)
- 排序(O(NlogN))，利用二分查找: logN
申请512M的内存
一个bit位代表一个unsigned int值
读入40亿个数，设置相应的bit位
读入要查询的数，查看相应bit位是否为1，为1表示存在，为0表示不存在
我们可以用每一个二进制位来记录一个数据，一个int本来只能记录一个数据的，现在可以记录64个数字了，大大减少的空间。
在小端存储的机器上是这样存储的：数据高字节保存在内存的高地址中,数据的低字节保存在低地址中。
比如我要把19记录进去
19/8=2
19%8=3
从0开始算，原本19/8=2，因此是在第三个字节当中，第3个位置(位置从0开始算)。
如何添加数据
如果我要把6这个数据添加到位图当中，初始化的位图的状态是全0。
如下图所示(位图的初始状态)：
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
6/8=0；
6%8=6；
因此就是在第0个字节中第6个位置。
可以构造出一个如下的二进制序列
| 0 | 1 | 0 | 0 | 0 | 0 | 0 | 0 |
将两个二进制序列**按位或（|）**一下，0|1=1，0|0=0，不会对其他位置的数据造成改变。
那么如何进行构造呢？
只要将1左移（<<）j个位置即可
1<<j。
如何删除数据
如果我要把6这个数据从位图当中删除
6/8=0；
6%8=6；
因此就是在第0个字节中第6个位置。
如下图所示(位图的初始状态)：
| 0 | 1 | 0 | 0 | 0 | 0 | 0 | 0 |
可以构造出一个如下的二进制序列
| 1 | 0 | 1 | 1 | 1 | 1 | 1 | 1 |
将两个二进制序列**按位与（&）**一下，0&1=0，0&0=0，1&1=1，不会对其他位置的数据造成改变。
那么如何进行构造呢？
只要将1左移（<<）j个位置然后按位取反即可
~(1<<j)。
代码实现
namespace mudan { template<size_t N> class bitset { public: bitset() { _bits.resize(N / 8 + 1, 0);//计算出需要多少字节来存储 } void set(size_t x) { size_t i = x / 8; size_t j = x % 8; _bits[i] |= (1 << j); } void reset(size_t x) { size_t i = x / 8; size_t j = x % 8; _bits[i] &= ~ (1 << j); } bool test(size_t x) { size_t i = x / 8; size_t j = x % 8; return _bits[i] & (1 << j); } private: vector<char> _bits; }; void test_bit_set1() { bitset<100> bs1; bs1.set(8); bs1.set(9); bs1.set(20); cout << bs1.test(8) << endl; cout << bs1.test(9) << endl; cout << bs1.test(20) << endl; cout <<"=====================" << endl; bs1.reset(8); bs1.reset(9); bs1.reset(20); cout << bs1.test(8) << endl; cout << bs1.test(9) << endl; cout << bs1.test(20) << endl; } }
测试结果可以看到正常运行了，可以查到找这个数字，删除之后就无法查找到了。
给100亿个整数，如何找到只出现一次的数字
可以用两个位图来记录情况
分类：
出现0次：00
出现1次：01
1次以上：10
代码实现
template<size_t N> class twobitset { public: void set(size_t x) { bool inset1 = _bs1.test(x); bool inset2 = _bs2.test(x); //00的情况 if (inset1 == false && inset2 == false) { //变成01，出现一次 _bs2.set(x); } else if (inset1 == false && inset2 == true) { //出现了一次，变成一次以上 _bs1.set(x);//1 _bs2.reset(x);//0 } else if (inset1 == true && inset2 == false) { //10->11 _bs1.set(x); _bs2.set(x); } } void print_once_num() { for (size_t i = 0; i < N; ++i) { if (_bs1.test(i) == false && _bs2.test(i) == true) { cout << i << endl; } } } private: bitset<N> _bs1; bitset<N> _bs2; }; void test_bit_set3() { int a[] = { 3, 4, 5, 2, 3, 4, 4, 4, 4, 12, 77, 65, 44, 4, 44, 99, 33, 33, 33, 6, 5, 34, 12 }; twobitset<100> bs; for (auto e : a) { bs.set(e); } bs.print_once_num(); }
可以看到，把只出现了一次的数字筛选出来了。
一次类推，出现两次三次四次五次六次都可以用这种方法。
给两个文件，分别有100亿个整数，但只有1g内存，如何找到文件的交集？
这个其实也简单，开两个位图，然后遍历位图是1 1就代表存在交集，反之没有。
1个文件有100亿个int，1G内存，设计算法找到出现次数不超过2次的所有整数
和之前的解决方式类似，记录几种状态
0次：00
1次：01
2次：10
3次及以上：11
