位图的介绍
经典面试题：
给40亿个不重复的无符号整数，没排过序。给一个无符号整数，如何快速判断一个数是否在这40亿个数中。
常用方法有：
1.先排序，在利用二分查找
2.将数据放到unorder_set中，利用find进行查找，判断是否在这些数中
方法1的时间复杂度：排序O(NlogN),二分查找O(logN)
方法2的时间复杂度：O(N)
这2个方法都还可以，但是40亿个无符号整数会占用内存约16GB，空间消耗非常的大，所以上面的2种方法就不行了。
那么用位图来解决
数据是否在给定的整形数据中，结果是在或者不在，刚好是两种状态，那么可以使用一个二进制比
特位来代表数据是否存在的信息，如果二进制比特位为1，代表存在，为0代表不存在。
例如：
无符号整数是2^32个字节，也就是521MB的大小，空间消耗变得很小了。
位图概念
位图，就是用每一位来存放某种状态，适用于海量数据，数据无重复的场景。通常是用来判断某个
数据存不存在的。
位图的应用
- 快速查找某个数据是否在一个集合中
- 排序
- 求两个集合的交集、并集等
- 操作系统中磁盘块标记
位图使用
位图的定义
方式一：构造1个16位的位图，所有初始化位是0
bitset<16> foo;
方式二：构造1个16位的位图，根据所给值初始化前n位
bitset<16> bar(0xf);
方式三：构造1个16位的位图，根据字符串的0,1序列初始化
bitset<16> baz(string("1000001"));
打印出来的效果：
位图的成员函数
| 成员函数 | 功能 |
|---|---|
| set | 设置定位或所有位 |
| reset | 清空指定位或所有位 |
| filp | 反转指定位或所有位 |
| test | 获取指定位的状态 |
| count | 获取被设置位的个数 |
| size | 获取可容纳的位的个数 |
| any | 如果有任何一个位被设置则返回true |
| none | 如果没有位被设置则返回true |
| all | 如果所有位都被设置则返回true |
void Testbiset2()
{
bitset<16> baz;
baz.set(8);
baz.set(10);
cout << baz << endl;
baz.reset(8);//清空第8位
cout << baz << endl;
baz.flip(8);//反转第8位
cout << baz << endl;
cout << baz.size() << endl;
cout << baz.any() << endl;
cout << baz.none() << endl;
cout << baz.all() << endl;
}
位图运算符的使用
1.bitset中对>>,<<重载过可以直接使用
bitset<8> baz;
cin >> baz;
cout << baz << endl;
2.对一些运算符的重载
赋值运算符：=
关系运算符：==、!=
复合赋值运算符：&=、|=、^=、<<=、>>=
单目运算符：~
bitset<4> foo(std::string("1001"));
bitset<4> bar(std::string("0011"));
cout << (foo ^= bar) << endl; // 1010
cout << (foo &= bar) << endl; // 0010
cout << (foo |= bar) << endl; // 0011
cout << (foo <<= 2) << endl; // 1100
cout << (foo >>= 1) << endl; // 0110
cout << (~bar) << endl; // 1100
cout << (bar << 1) << endl; // 0110
cout << (bar >> 1) << endl; // 0001
cout << (foo == bar) << endl; // false
cout << (foo != bar) << endl; // true
cout << (foo & bar) << endl; // 0010
cout << (foo | bar) << endl; // 0111
cout << (foo ^ bar) << endl; // 0101
3.opeartor[],直接对某位进行修改或访问
bitset<4> bar;
bar[1] = 1;
bar[2] = bar[1];
cout << bar << endl;
位图的模拟实现
构造函数
我们需要根据所给的N来构造N位的位图，并且将位图中的所有位初始化位0
1个整形是32个比特位，N位的位图就是N/32，但是N可能不是32的整数倍还需要+1。
bitset()
{
_bits.resiez(N / 32 + 1,0);
}
set、reset、filp
set设置位
设置位图中指定位的方法：
1.计算出是第i个数的第j位
2.将1左移j位后和第i个位进行或运算
代码如下：
void set(size_t pos)
{
assert(pos < N);
//计算pos映射在第几个数的多少位
int i = pos / 32;
int j = pos % 32;
_bits[j] |= (1 << j);//将该位置设为1
}
reset清空位
清空位图中指定位的方法：
1.计算出是第i个数的第j位
2.将1左移j位再整体取反与第i个数相与
代码如下：
void reset(size_t pos)
{
assert(pos < N);
//计算pos映射在第几个数的多少位
int i = pos / 32;
int j = pos % 32;
_bits[j] &= (~(1 << j));//左移取反在相与
}
filp反转指定位
1.计算出是第i个数的第j位
2.将1左移j位后和第i个位进行异或运算
void filp(size_t pos)
{
assert(pos < N);
int i = pos / 32;
int j = pos % 32;
_bits[j] ^= (1 << j);//左移在取反
}
size、count
size直接返回N即可
size_t size()
{
return N;
}
count获取位图中设置位的个数
逻辑如下：
1.将原数n与n-1与运算得到新数n
2.判断n是否为0，不为0继续进行第1步
size_t count()
{
size_t count = 0;
//将每个整数中1的个数累加起来
for (auto e : _bits)
{
int num = e;
//计算整数num中1的个数
while (num)
{
num = num & (num - 1);
count++;
}
}
return count; //位图中1的个数，即被设置位的个数
}
其他的接口博主就没有实现，主要都是位运算的操作。