位图
腾讯面试题：给 40 亿个不重复的无符号整数，没排过序，给一个无符号整数，如何快速判断一个数是否在 40 亿个数中。
- 遍历？？时间复杂度为 O(N)
- set 使用红黑树？？
40 亿个整数等于 160 亿 byte，1G 等于 1024MB 等于 10241024KB 等于 10241024*1024Byte，换算过来 1G 等于 10 亿 Byte，那么 160 亿 Byte 大约等于 16G。这种情况也仅仅只是使用顺序表来存储，如果使用容器（红黑树），那么内存消耗会更大。
可以利用哈希的直接定址法，如果需要确定的值有 42 亿个值，可以通过 2^32bit 位置来确定对应值是否存在，1 个字节有 8 个 bit 位也就是可以确定 2^8，此时 42 亿个数据需要 2^29 字节，即 500MB 的内存空间即可。
通过在顺序表中保存 int 的值，一个 int 有 4 个字节也就是代表 32 个值，如果需要存储例如 80，只需要用 80 / 32 = 2，也就是 80 在下标为 2 的 int 值中的第 80%32 的 bit 位置。
【科普】计算机底层存储可能是按照大端机，也可能是小端机存储方式。
#pragma once
#include <vector>
#include <iostream>
using namespace std;
template<size_t N>
class BitSet {
public:
BitSet() { _a.resize(N / 32 + 1); }
// 将 x 映射的值标记成 1
void set(size_t x) {
size_t i = x / 32;
size_t j = x % 32;
_a[i] |= ( << j);
}
{
i = x / ;
j = x % ;
_a[i] &= ~( << j);
}
{
i = x / ;
j = x % ;
_a[i] & ( << j);
}
:
vector<> _a;
};
