本文旨在讲解位图的原理，以及位图有什么作用，如何实现位图。希望读完本篇文章能对小伙伴们有一定的收获！上干货！
什么是位图
位图就是bitmap的缩写，所谓bitmap，就是用每一位来存放某种状态，适用于大规模数据，该数据都是不重复的简单数据。通常是用来判断某个数据存不存在的。
C++中以bitset定义为位图，下面我们来看一下C++对位图的解释吧！
在C++中，位图以非类型的模版参数定义，简单翻译下来就是：位图存储比特位（其存储的元素只有0/1两个值）。
位图的应用：（海量数据的处理）
位图通常用于海量数据的处理！
例如如果有40亿个无符号整数，那么如何快速判断一个数是否存在与这40亿个无符号整数数中呢？
可能有的小伙伴首先想到的就是遍历一遍数组，然后判断即可！那么如果是否真的能遍历呢？对于40亿个无符号整数，其占用大约15G的空间！
40亿*4=160亿字节/1024/1024/1024=14.9
对于40亿个数字，大约占了15G内存，大多计算机根本放不下这么大的数据！那么该如何解决呢？此时就引进了位图，位图其只用一个比特位代表一个数字！所以40亿个比特位就转化为内存大约为：40亿/8/1024/1024/1024 =0.46G,占用不到0.5G的内存，显然使用位图的方式可以解决！那么该如何使用位图呢？
我们只需要求出这个数字对应于位图的哪一位即可，如果该数字存在，那么就将改为置为1即可，否则就置为0。
对于位图，我们定义一个vector<char>的向量，每个元素为char类型的，占8个字节！我们只需要求出数字在这个vector中对应的位置即可，存在的话，将对应为设为1，下面来看一个例子！
对于数字1,5,7,15,22，在位图中就是这样存储的！
这是怎么计算的呢？下面来讲解一下：对于vector,内部放的是char类型的，因为char占8个字节，所以我们只需要将数字除一个8，就能得到在第几个字节中，然后进行取余，就可以得到在当前字节的第几个比特位！
例如15
15/8=1 15%8=7；所以15就在下标为1的那个字节中，在当前字节中的第7个比特位！其他也是同理的！
既然了解了位图的存储方式，那么我们就来简单实现一下位图这个结构吧！
实现位图
参考C++中的位图的一些功能，我们就简单实现一些位图的操作！
我们就来简单实现test(),set(),reset(),这几个函数吧！
set()函数的实现
通过观察C++文档， 我们可以得知，set的作用是将对应的比特位设置为true即为1！
下面我们就来自己实现这个set函数，因为位图的结构是我们自己定义的，那么当我们将位图的底层用vector<int>向量来进行实现的话，我们只需要将除的值和模的值都变成int的比特位即可！
下面我们就以vector<int>向量来进行实现！
//实现set函数！
//观察库中的set函数，我们可以发现set函数是将x对应的比特位置为1！
void set(size_t x)
{
//i代表数组中的第几个下标！
int i = x / 32;
//j代表的是该下标的第几个比特位！
int j = x % 32;
//然后将数组中i位置的第j个比特位置为1即可！
//将第几个比特位置为1，我们可以使用按位或上1即可！
_bitset[i] |= 1 << j;
}将某一位设置为1，前面我的文章已经讲过了，我也不过多进行解释了，只需要将1左移j位，然后按位与上1即可！
reset()函数的实现！
我们实现库中的第二个reset函数，将pos位置为0。代码如下
//reset的作用是将x对应的位重置为0！
void reset(size_t x)
{
//i代表数组中的第几个下标！
int i = x / 32;
//j代表的是该下标中的第几个比特位！
int j = x % 32;
//将第i为置为0的操作，只需要进行按位于上个(1左移x=位取反！)即可！
_bitset[i] &= ~(1 << j);
}
我们将某一位置为0只需要进行将1进行左移j位，然后取反按位与即可!!
test()函数的实现！
test()函数用于检验当前位是否被设置，如果被设置就返回true，否则返回false，即判断当前位是否为1，为1返回true，为0返回false!
bool test(size_t x)
{
//i代表数组中的第几个下标！
int i = x / 32;
//j代表的是该下标中的第几个比特位！
int j = x % 32;
//按位与上个1左移j位
return _bitset[i]&(1 << j);
}至此位图相关函数已经实现，下面我们看一下位图的成员的实现，以及构造函数！
成员就是我们刚才讲的，其中vector中的类型可以换成char，long long 等类型！
对于构造函数！
因为是vector容器，其resize的参数默认是n个存储元素的大小，所以我们多开辟一个该类型的空间，防止因不能整除导致空间不够的问题！
位图实现的所有代码
#pragma once
//自己模拟实现位图的操作！
//加上命名空间与库中的bitset进行区分
#include<vector>
namespace Zhj
{
//非类型的模版！
template<size_t N>
class Bitset
{
public:
//构造函数！
Bitset()
{
//对位图进行初始化！
//为容器分配空间，因为是整形类型的容器，所以需要开辟N/32 但是可能除不尽，所以多开辟一个int的空间！
_bitset.resize(N / 32 + 1);
}
//实现set函数！
//观察库中的set函数，我们可以发现set函数是将第x为置为1！
void set(size_t x)
{
//i代表数组中的第几个下标！
int i = x / 32;
//j代表的是该字节中的第几个比特位！
int j = x % 32;
//然后将数组中i位置的第j个比特位置为1即可！
//将第几个比特位置为1，我们可以使用按位或上1即可！
_bitset[i] |= 1 << j;
}
//reset的作用是将第x为重置为0！
void reset(size_t x)
{
//i代表数组中的第几个下标！
int i = x / 32;
//j代表的是该字节中的第几个比特位！
int j = x % 32;
//将第i为置为0的操作，只需要进行按位于上个(1左移x=位取反！)即可！
_bitset[i] &= ~(1 << j);
}
//检测第x位是什么！
bool test(size_t x)
{
//i代表数组中的第几个下标！
int i = x / 32;
//j代表的是该字节中的第几个比特位！
int j = x % 32;
//按位与上个1左移j位
return _bitset[i]&(1 << j);
}
private:
//默认以存储int类型来构造！
vector<int> _bitset;
};
}海量数据的处理
既然了解了位图，以及其实现，那么我们就来看一些关于位图的题目吧！
1.给定100亿个整数，设计算法找到只出现一次的整数？
对于这道题，首先想到的肯定是使用位图，因为如果不使用位图，内存空间是肯定不够的！那么我们该如何使用位图来解决问题呢?
对于整数类型，其取值范围为0~2^32-1;对于100亿个数字，肯定是存在重复的，那么我们就需要创建两个位图，用于统计出现的次数！
位图1 s1， 位图2 s2。
我们可以这样进行统计次数！
0 0 代表0次！
0 1 代表一次！
1 0 代表两次即以上！
我们只需要创建两个位图将该数字对应的位数进行统计即可！我们可以使用库中的bitset，来实现，我们自己来实现一个由两个位图构成的位图！
#include<bitset>
#include<iostream>
#include<vector>
using namespace std;
template<size_t N>
class twobitset
{
public:
void set(size_t x)
{
//00 --> 01
if (_b1.test(x) == false && _b2.test(x) == false)
{
_b2.set(x); //一次！
}
//01->10
else if (_b1.test(x) == false && _b2.test(x) == true)
{
_b1.set(x); //两次及以上！
_b2.reset(x);
}
}
void printonce()
{
for (size_t i = 0; i < N; i++)
{
if (_b1.test(i) == false && _b2.test(i) == true)
{
cout << i<<endl;
}
}
}
private:
bitset<N> _b1;
bitset<N> _b2;
};下面来看测试函数！
#define _CRT_SECURE_NO_WARNINGS 1
#include"TwoBitset.h"
#include<bitset>
int main()
{
twobitset<100> bs;
int a[] = { 1,51,34,5,16,7,9,8,8,9,51 };
for (auto ch : a)
{
bs.set(ch);
}
bs.printonce();
return 0;
}运行结果如下：
确实把我们只出现一次的数字进行的打印出来，那么将100亿个整数放入，那也是可以的！
2. 给两个文件，分别有100亿个整数，我们只有1G内存，如何找到两个文件交集？
因为还是海量数据，所以还是使用的位图思想，我们需要创建两个位图，然后将这100亿个数字利用set函数放到位图中，然后将这两个位图的各个位置进行按位与，把按位与的结果最后利用test函数检测为1的状态，为1的就是交集！
3. 位图应用变形：1个文件有100亿个int，1G内存，设计算法找到出现次数不超过2次的所有整数。
与第一题一样，只不过需要多加一个条件即可！即出现两次的也要打印，所以我们也要记录10的存在，当两次以上的结果我们记录为11即可即可！代码如下：
#include<bitset>
#include<iostream>
#include<vector>
using namespace std;
template<size_t N>
class twobitset
{
public:
void set(size_t x)
{
//00 --> 01
if (_b1.test(x) == false && _b2.test(x) == false)
{
_b2.set(x); //一次！
}
//01->10
else if (_b1.test(x) == false && _b2.test(x) == true)
{
_b1.set(x); //两次！
_b2.reset(x);
}
else if (_b1.test(x) == true && _b2.test(x) == false)
{
_b2.set(x); //两次以上的情况！
}
}
void prinlesstwo()//打印两次及以下！
{
for (size_t i = 0; i < N; i++)
{
if (_b1.test(i) == false && _b2.test(i) == true)
{
cout << i<<endl;
}
else if (_b1.test(i) == true && _b2.test(i) == false)
{
cout << i << endl;
}
}
}
private:
bitset<N> _b1;
bitset<N> _b2;
}; 至此，位图的相关介绍已经完毕，希望读完本篇文章，能对读者有一定的收获！
