目录
一、什么是位图
二、位图类
1.参数及构造函数
2.set函数设置为1（代表存在）
3.reset函数设置为0（代表不存在）
4.test函数查看状态（0还是1）
三、位图的变形
一、什么是位图
位图这个词汇比较少见，在学习位图之前，我们可以先来看看下面这个问题
40亿个数，大约为2^32。 这里有几个方案解决
解决方案1：暴力查找，将数据遍历一遍直到找到，但是40亿个数据太大了，如果换算为整数，那么至少需要16G（4*2^32代表4个字节，再乘以个数）的内存，一般的电脑是没办法开辟出这么大的连续空间的。
解决方案2：就是已经是有序了，我们只需二分查找，二分查找的效率为log(n)，但这里跟效率没啥关系，主要还是无法开辟这么大的内存的问题
解决方案3：将数据放到unordered_set或者set中，使用哈希表和红黑树的思想帮我们查找，但是哈希表和红黑树他们存放的结点会占用更多的空间，因为存放的结点不仅仅有数据，还有指针，因此更无法使用。
前面的几个解决方案都没有办法解决这种较大数据的问题，那么我们引入概念位图。
每一个值映射一个bit位，那么我们只需要一个bit位就可以知道该位置的值是否存在了，0为不存在，1为存在。这就叫做位图。
那么40亿个数据按照这种方法来表示他们是否存在的状态，只需要0.5G(2^32/8 代表所有的数据除以每个字节的8位)
二、位图类
其实库里面也有bitset位图，我们模仿一下这个位图的基本函数。
1.参数及构造函数
我们写出一个类，类的模板参数只有一个常量，代表我们要存放多少个数据的状态(bit位)，类成员为vector<int> _bits;
同时构造参数是给_bits开辟足够的空间，_bits.resize(N / 32 + 1, 0); N/32代表一个整形的每一个bit位都存放状态，+1是为了防止除数把余数丢掉，比如40/32==1，如果我们只开辟一个int整形，就会将后面的数据丢掉。
template<size_t N>
class bitset
{
public:
bitset()
{
_bits.resize(N / 32 + 1, 0);
}
private:
vector<int> _bits;
}2.set函数设置为1（代表存在）
有了这个，我们如何来设置，让我们想要映射的位置变为1呢？
首先，参数部分肯定需要一个整数，代表是这个数据，我们可以通过 x/32 来表示映射到哪一个整形里了，再通过 x%32来表示映射该整形的哪一个bit位。这样我们就可以找到映射的位置了，找到位置后，应该如何将他的值赋为1呢？
我们的想法是让他无论是为0还是为1，我都要设置为1，这样初步会考虑到 |（或运算），肯定是 | 上1，我们可以通过左移运算符，将1左移到想要的位置，也就是 j 位置。这样进行或运算，就可以保证在不影响其他位置的值的前提，将想要的位置置为1了。
代码如下
void set(size_t x)
{
int i = x / 32;
int j = x % 32;
_bits[i] |= (1 << j);
}3.reset函数设置为0（代表不存在）
有了设置存在，我们也得设置不存在，如何操作呢？
一样的方法先找到 i 和 j ,无论该值为1还是为0，要想设置为0，就需要&(与运算)0才行，那我们将 1 左移 j 位，再取反，就让想要的bit位变成了0，其他位都为1。
任何数(指0和1)与上1都是他本身，这样就没有改变其他bit位，任何数与上0都为0，这样就达到我们的设置改bit位为 0 目的了。
代码如下
void reset(size_t x)
{
int i = x / 32;
int j = x % 32;
_bits[i] &= ~(1 << j);
}4.test函数查看状态（0还是1）
有了置为1和置为0，我们还需要去查看该位置的状态。
依然是计算出 i 和 j ，与上(1<<j)返回即可，因为任何数(指0和1)与上1都是他本身，因此我们状态为0就返回0，为1就返回1，就知道该位置的状态了。
bool test(size_t x)
{
int i = x / 32;
int j = x % 32;
return _bits[i] & (1 << j);
}测试一下，没有问题，这样就极大的节省了空间。
三、位图的变形
如下面这个题，就是位图的变形题。
这里也有两个方案去解决。
方案1：将单位图修改为双位图，从整形存放32个状态（0或1），编程存放16个（00或01或10）状态。由于找到只出现一次的整数，那么状态我们只需要设置（00或01或10）分别代表0个、1个、2个及以上。这个方案虽然可行，但是要重新修改位图，比较麻烦。
方案2：再写一个类，变量为两个位图，第一个位图代表状态（00或01或10）的前一个bit位，第二个位图代表状态（00或01或10）的后一个bit位。
很明显，代码复用要香很多，我们选择方案2。
set函数中，如果bit1的test(x)为false，bit2的test(x)也为false，那么就将bit2的该位置设置为1。
如果bit1的test(x)为false，bit2的test(x)为true，就将bit1位置设置为1，bit2位置设置为0，就完成了。
再写一个打印函数就完成了。
具体代码如下
template<size_t N>
class twobitset
{
public:
void set(size_t x)
{
if (bit1.test(x) == false && bit2.test(x) == false)
{
bit2.set(x);
}
else if (bit1.test(x) == false && bit2.test(x) == true)
{
bit1.set(x);
bit2.reset(x);
}
}
void PrintOnce()
{
for (size_t i = 0; i < N; i++)
{
if (bit1.test(i) == false && bit2.test(i) == true)
{
cout << i << endl;
}
}
cout << endl;
}
private:
bitset<N> bit1;
bitset<N> bit2;
};代码测试，没问题。
该位图只涉及到了整数的处理，如果是字符串怎么处理呢？需要用到布隆过滤器，这个我们下次再讲。
最后附上总代码
bitset.h
#pragma once
#include<vector>
namespace kky
{
template<size_t N>
class bitset
{
public:
bitset()
{
_bits.resize(N / 32 + 1, 0);
}
void set(size_t x)
{
int i = x / 32;
int j = x % 32;
_bits[i] |= (1 << j);
}
void reset(size_t x)
{
int i = x / 32;
int j = x % 32;
_bits[i] &= ~(1 << j);
}
bool test(size_t x)
{
int i = x / 32;
int j = x % 32;
return _bits[i] & (1 << j);
}
private:
vector<int> _bits;
};
template<size_t N>
class twobitset
{
public:
void set(size_t x)
{
if (bit1.test(x) == false && bit2.test(x) == false)
{
bit2.set(x);
}
else if (bit1.test(x) == false && bit2.test(x) == true)
{
bit1.set(x);
bit2.reset(x);
}
}
void PrintOnce()
{
for (size_t i = 0; i < N; i++)
{
if (bit1.test(i) == false && bit2.test(i) == true)
{
cout << i << endl;
}
}
cout << endl;
}
private:
bitset<N> bit1;
bitset<N> bit2;
};
}test.cpp
#include<iostream>
using namespace std;
#include"bitset.h"
//int main()
//{
// kky::bitset<100> bs;
// bs.set(10);
// bs.set(11);
//
// cout << bs.test(9) << endl;
// cout << bs.test(10) << endl;
// cout << bs.test(11) << endl;
// cout << bs.test(12) << endl;
// bs.reset(10);
// cout << bs.test(10) << endl;
//}
int main()
{
int a[] = { 1,3,4,6,8,4,6,3,1,5,7 };
kky::twobitset<100> bs;
for (auto e : a)
{
bs.set(e);
}
bs.PrintOnce();
}谢谢大家观看！！！
