ps：左移位并不是向左移动位，而是低数据位向高数据位挪动
位图（主要接口，set(size_t)标识、reset(size_t)取消、test(size_t) 查看
给40亿个不重复的无符号整数，没排过序。给一个无符号整数，如何快速判断一个数是否在 这40亿个数中。【腾讯】
这么多的数据根本无法在内存中存储，所以，将他们放进set，map中这是不切实际的。
遍历一遍数据，也许可以，但是如果再来一个查找值，难道还要再遍历一遍吗？再来再遍历？
注意审题：
- 我们会发现，我们并不需要将数据存储起来，我们只是需要知道，他是否存在于这40亿个数中，所以我们只需要判断40个亿中有没有该数。
- size_t类型的数据范围是0~40亿多，如果普通的哈希创建size_t类型的数组来标识下标对应的是否重载，我们需要4*40亿个字节的空间=>16个G的内存，机器不说能不能存下，就是是64位存下了，那么我们的操作系统怎么办？？？
构造位图bit_set
成员变量：
template <size_t N>
class bitset
{
//........
private:
vector<char> _map;//图的意思
}注意我们其实只是想知道是否存在，标识40亿个数据罢了，并不是真的要存储40亿个数据，所以我们使用计算机存储单位最小的类型比特位来存储数据，应为size_t类型范围的最小是0，最大是42亿多，所以这道题我们需要直接创建42亿个比特位来存储，数组下标的位置映射元素是否存在该数，1标识存在，0标识不存在。注意我们无法直接创建比特类型的数组，我们需要创建其他类型，然后位处理比特位。所以我们创建char类型的数组来映射比特数组。
所以我们的数组只需要开char[40亿/8]大小的数组(一个char可以标识8个数据)
这样我们存在的问题，就不需要考虑类型了，只需要考虑个数问题。
构造函数代码
bitset()
{
_bits.resize(N/8+1,0);//将所有位初始化为0
}标识数据位set(size_t)
我们需要把这40亿个size_t 数据标识到位图中。
例：我们将40亿中的26数据标识到位图中
2步走
- 寻找需要标识的位置
- 标识比特位为1
寻找数据标识位：
我们确定了26数据存储在map[3]的第二个比特位，
修改标记数据位为1：
我们现在需要把这个位置的bite位给标记为1，该如何呢？
我们需要对该位置继续位操作，
使用位运算符号|对图中该位置改为1，并且其他位置不动，所以我们需要一个数据同位为1，其他位为0，与图的该char类型元素进行逻辑或运算，
这样，该位无论是什么在或上1都被标识为1，其他位或上0先前是什么，现在依旧是什么
这样我们的数据就标识完毕。
代码：
void bit_set::set(size_t x)
{
int loction = x / 8;
int bitloction = x % 8;
char flag = 1;
flag = flag << bitloction;
_bits[loction] |= flag;
}取消标识位( reset() )
假设我们把刚刚set的数据26 reset()取消掉
2步走
- 寻找需要标识的位置
- 标识比特位为0
寻找数据标识位
首先也是寻找位和我们之前set（）操作是一样的，
数据/8得：map得下标元素，
数据%8得：标识该元素得比特位
所以我们跳过寻找逻辑。
修改标记数据位为0：
修改得逻辑其实和之前是一样的，但是我们现在需要的是将该位置标识为0，其他位置不变，
需要对数据标记位逻辑与0，保证该其位置标识改变为0（不论操作标识位是什么都改为0）
需要对其它位置逻辑与1，保证其他位置标识不受到改变为0（不论其他标识位是什么，都不能改变）
然后也是对数据1进行位运算操作~直接上图
这样，该位无论是什么在与上0都被标识为0，其他位与上1先前是什么，现在依旧是什么
这样我们的数据就取消标识。
代码：
void reset(size_t x)
{
int loction = x / 8;
int bitloction = x % 8;
char flag = 1;
flag = flag << bitloction;
flag=(~flag);
_bits[loction] &= flag;
}查看数据是否已标识 test（）
现在我们并不知道该26数据是否在位图中。
2步走
- 寻找需要标识的位置
- 查看标识位
寻找数据标识位
首先也是寻找位和我们之前set（）操作是一样的，
数据/8得：map得下标元素，
数据%8得：标识该元素得比特位
所以我们跳过寻找逻辑。
查看该位置是否为被标识
获取到了，我们只需要找到该位数据存不存在并不怎么样，所以我们只需要真假，不关心是具体数据是什么。
所以我们将该char元素其他的比特位置0，其用比特位1与其按位与，检查其是否存在。
所以我们需要map[3]:10X0 1101 -> 00X0 0000 的数据，获取辅助数据的方法与set()一样。
注意，test实现不可改变map[3]的值，所以保存到一个变量，或者按位与数据返回
代码：
bool test(size_t x)
{
int loction = x / 8;
int bitloction = x % 8;
char flag = 1;
flag = flag << bitloction;
return _bits[loction] & flag;
// bool tmp=_bits[loction] & flag;
// return tmp;
}回到上题：给40亿个不重复的无符号整数，没排过序。给一个无符号整数，如何快速判断一个数是否在 这40亿个数中。【腾讯】
1、bitset<-1> _map; 范围开size_t的取值范围 42亿多个比特位
2、_map.set(40亿size_t); 将40亿个数据映射到位图中
3、cout<<_map.test(查找的数据) 查看数据是否在位图中，1就是在，0就是不在
完成
完整代码：
template <size_t N>
class bitset
{
public:
bitset()
{
_bits.resize(N / 8 + 1, 0);
}
void set(size_t x)
{
int loction = x / 8;
int bitloction = x % 8;
char flag = 1;
flag = flag << bitloction;
_bits[loction] |= flag;
}
void reset(size_t x)
{
int loction = x / 8;
int bitloction = x % 8;
char flag = 1;
flag = flag << bitloction;
_bits[loction] &= (~flag);
}
bool test(size_t x)
{
int loction = x / 8;
int bitloction = x % 8;
char flag = 1;
flag = flag << bitloction;
return _bits[loction] & flag;
}
private:
vector<char> _bits;
};