bitset（位图）
位图引入
要判断一个数是否在某一堆数中，我们可能会想到如下方法：
- 将这一堆数进行排序，然后通过二分查找的方法判断该数是否在这一堆数中。
- 将这一堆数插入到unordered_set容器中，然后调用find函数判断该数是否在这一堆数中。
单从方法上来看，这两种方法都是可以，而且效率也不错，第一种方法的时间复杂度是O ( N l o g N ) ，第二种方法的时间复杂度是O ( N )。
但问题是这里有40亿个数，若是我们要将这些数全部加载到内存当中，那么将会占用16G的空间，空间消耗是很大的。因此从空间消耗来看，上面这两种方法实际都是不可行的。
位图解决
实际在这个问题当中，我们只需要判断一个数在或是不在，即只有两种状态，那么我们可以用一个比特位来表示数据是否存在，如果比特位为1则表示存在，比特位为0则表示不存在。比如：
无符号整数总共有232个，因此记录这些数字就需要232个比特位，也就是512M的内存空间，内存消耗大大减少。
位图的概念
所谓位图，就是用每一位来存放某种状态，适用于海量数据，数据无重复的场景。通常是用来判断某个数据存不存在的。
位图的应用
常见位图的应用如下：
- 快速查找某个数据是否在一个集合中。
- 排序。
- 求两个集合的交集、并集等。
- 操作系统中磁盘块标记。
- 内核中信号标志位（信号屏蔽字和未决信号集）。
bitset的使用
bitset的定义方式
//方式一： 构造一个16位的位图，所有位都初始化为0。
bitset<16> bs1; //0000000000000000
//方式二： 构造一个16位的位图，根据所给值初始化位图的前n位。
bitset<16> bs2(0xfa5); //0000111110100101
//方式三： 构造一个16位的位图，根据字符串中的0/1序列初始化位图的前n位。
bitset<16> bs3(string("10111001")); //0000000010111001
bitset成员函数的使用
bitset中常用的成员函数如下：
使用示例：
#include <iostream>
#include <bitset>//注意引入头文件
using namespace std;
int main()
{
bitset<8> bs;
bs.set(2); //设置第2位
bs.set(4); //设置第4位
cout << bs << endl; //00010100
bs.flip(); //反转所有位
cout << bs << endl; //11101011
cout << bs.count() << endl; //6
cout << bs.test(3) << endl; //1
bs.reset(0); //清空第0位
cout << bs << endl; //11101010
bs.flip(7); //反转第7位
cout << bs << endl; //01101010
cout << bs.size() << endl; //8
cout << bs.any() << endl; //1
bs.reset(); //清空所有位
cout << bs.none() << endl; //1
bs.set(); //设置所有位
cout << bs.all() << endl; //1
return 0;
}
注意： 使用成员函数set、reset、flip时，若指定了某一位则操作该位，若未指定位则操作所有位。
bitset运算符的使用
bitset容器对>>、<<运算符进行了重载，我们可以直接使用>>、<<运算符对biset容器定义出来的对象进行输入输出操作。
#include <iostream>
#include <bitset>
using namespace std;
int main()
{
bitset<8> bs;
cin >> bs; //10110
cout << bs << endl; //00010110
return 0;
}
bitset容器中不仅对赋值运算符和一些关系运算符进行了重载，而且对一些复合赋值运算符和单目运算符也进行了重载，我们可以直接使用这些运算符对各个位图进行操作。
包括如下运算符：
- 赋值运算符：=。
- 关系运算符：==、!=。
- 复合赋值运算符：&=、|=、^=、<<=、>>=。
- 单目运算符：~。
#include <iostream>
#include <string>
#include <bitset>
using namespace std;
int main()
{
bitset<8> bs1(string("10101010"));
bitset<8> bs2(string("10101010"));
bs1 >>= 1;
cout << bs1 << endl; //01010101
bs2 |= bs1;
cout << bs2 << endl; //11111111
return 0;
}
bitset容器中同时也对三个位运算符进行了重载，我们可以直接使用&、|、^对各个位图进行操作。
#include <iostream>
#include <string>
#include <bitset>
using namespace std;
int main()
{
bitset<8> bs1(string("10101010"));
bitset<8> bs2(string("01010101"));
cout << (bs1&bs2) << endl; //00000000
cout << (bs1|bs2) << endl; //11111111
cout << (bs1^bs2) << endl; //11111111
return 0;
}
bitset容器中对[ ]运算符进行了重载，我们可以直接使用[ ]对指定位进行访问或修改。
#include <iostream>
#include <string>
#include <bitset>
using namespace std;
int main()
{
bitset<8> bs(string("00110101"));
cout << bs[0] << endl; //1
bs[0] = 0;
cout << bs << endl; //00110100
return 0;
}
bitset（位图）的模拟实现
bitset类各函数接口总览
namespace cl
{
//模拟实现位图
template<size_t N>
class bitset
{
public:
//构造函数
bitset();
//设置位
void set(size_t pos);
//清空位
void reset(size_t pos);
//反转位
void flip(size_t pos);
//获取位的状态
bool test(size_t pos);
//获取可以容纳的位的个数
size_t size();
//获取被设置位的个数
size_t count();
//判断位图中是否有位被设置
bool any();
//判断位图中是否全部位都没有被设置
bool none();
//判断位图中是否全部位都被设置
bool all();
//打印函数
void Print();
private:
vector<int> _bits; //位图
};
}
注：为了防止与标准库当中的bitset类产生命名冲突，模拟实现时需放在自己的命名空间当中。
bitset类的实现
构造函数
一个整型有32个比特位，因此N个位的位图就需要用到N/32个整型，但是实际我们所需的整型个数是N/32+1，因为所给非类型模板参数N的值可能并不是32的整数倍。
代码如下：
//构造函数
bitset()
{
_bits.resize(N / 32 + 1, 0);
}
set、reset、flip、test
设置位图中指定的位的方法如下：
- 计算出该位位于第 i 个整数的第 j 个比特位。
- 将1左移 j 位后与第 i 个整数进行或运算即可。
代码：
//设置位
void set(size_t pos)
{
assert(pos < N);
//算出pos映射的位在第i个整数的第j个位
int i = pos / 32;
int j = pos % 32;
_bits[i] |= (1 << j); //将该位设置为1（不影响其他位）
}
清空位图中指定的位的方法如下：
- 计算出该位位于第 i 个整数的第 j 个比特位。
- 将1左移 j 位再整体反转后与第 i 个整数进行与运算即可。
代码:
//清空位
void reset(size_t pos)
{
assert(pos < N);
//算出pos映射的位在第i个整数的第j个位
int i = pos / 32;
int j = pos % 32;
_bits[i] &= (~(1 << j)); //将该位设置为0（不影响其他位）
}
//注意： ！-> 逻辑取反
// ~ -> 按位取反
反转位图中指定的位的方法如下：
- 计算出该位位于第 i 个整数的第 j 个比特位。
- 将1左移 j 位后与第 i 个整数进行异或运算即可。
代码如下：
//反转位
void flip(size_t pos)
{
assert(pos < N);
//算出pos映射的位在第i个整数的第j个位
int i = pos / 32;
int j = pos % 32;
_bits[i] ^= (1 << j); //将该进行反转（不影响其他位）
}
获取位图中指定的位的状态的方法如下：
- 计算出该位位于第 i 个整数的第 j 个比特位。
- 将1左移 j 位后与第 i 个整数进行与运算得出结果。
- 若结果非0，则该位被设置，否则该位未被设置。
代码：
//获取位的状态
bool test(size_t pos)
{
assert(pos < N);
//算出pos映射的位在第i个整数的第j个位
int i = pos / 32;
int j = pos % 32;
if (_bits[i] & (1 << j)) //该比特位被设置
return true;
else //该比特位未被设置
return false;
}
size、count
我们直接将所给非类型模板参数进行返回即可。
//获取可以容纳的位的个数
size_t size()
{
return N;
}
获取位图中被设置的位的个数，也就是统计位图中1的个数，我们只需要依次统计每个整数二进制中1的个数，然后将其相加即可得到位图中1的个数。
统计二进制中1的个数的方法如下：
- 将原数 n 与 n - 1 进行与运算得到新的 n 。
- 判断 n 是否为0，若 n 不为0则继续进行第一步。
如此进行下去，直到 n 最终为0，此时该操作进行了几次就说明二进制中有多少个1,因为该操作每进行一次就会消去二进制中最右边的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的个数，即被设置位的个数
}
any、none、all
我们只需遍历每一个整数，若这些整数全部都为0，则说明位图中没有位被设置过。
虽然位图可能并没有包含最后一个整数的全部比特位，但由于我们构造位图时是将整数的全部比特位都初始化成了0，因此不会对此处判断造成影响。
代码：
//判断位图中是否有位被设置
bool any()
{
//遍历每个整数
for (auto e : _bits)
{
if (e != 0) //该整数中有位被设置
return true;
}
return false; //全部整数都是0，则没有位被设置过
}
位图中是否全部位都没有被设置，实际上就是位图中有位被设置的反面，因此none成员函数直接调用any成员函数，然后将返回值取反后再进行返回即可。
代码:
//判断位图中是否全部位都没有被设置
bool none()
{
return !any();
}
判断过程分为两步：
- 先检查前n-1个整数的二进制是否为全1。
- 再检查最后一个整数的前N%32个比特位是否为全1。
需要注意的是，如果位图没有包含最后一个整数的全部比特位，那么最后一个整数的二进制无论如何都不会为全1，所以在判断最后一个整数时应该只判断位图所包含的比特位。
代码：
//判断位图中是否全部位都被设置
bool all()
{
size_t n = _bits.size();
//先检查前n-1个整数
for (size_t i = 0; i < n - 1; i++)
{
if (~_bits[i] != 0) //取反后不为全0，说明取反前不为全1
return false;
}
//再检查最后一个整数的前N%32位
for (size_t j = 0; j < N % 32; j++)
{
if ((_bits[n - 1] & (1 << j)) == 0) //该位未被设置
return false;
}
return true;
}
打印函数
可以实现一个打印函数，便于检查我们上述代码的正确性，打印位图时遍历位图所包含的比特位进行打印即可，在打印位图的过程中可以顺便统计位图中位的个数count，将count与我们传入的非类型模板参数N进行比较，可以判断位图大小是否是符合我们的预期。
//打印函数
void Print()
{
int count = 0;
size_t n = _bits.size();
//先打印前n-1个整数
for (size_t i = 0; i < n - 1; i++)
{
for (size_t j = 0; j < 32; j++)
{
if (_bits[i] & (1 << j)) //该位被设置
cout << "1";
else //该位未被设置
cout << "0";
count++;
}
}
//再打印最后一个整数的前N%32位
for (size_t j = 0; j < N % 32; j++)
{
if (_bits[n - 1] & (1 << j)) //该位被设置
cout << "1";
else //该位未被设置
cout << "0";
count++;
}
cout << " " << count << endl; //打印总共打印的位的个数
}
The end