目录
一.问题导入
二.什么是位图?
2.1如何确定目标数在哪个比特位?
2.2如何存放高低位
2.3位图模拟代码实现
2.3.1如何标记一个数
2.3.2如何重置标记
2.3.3如何检查一个数是否被标记
整体代码实现
标准库的Bitset
库中的bitset的缺陷
简单应用
一.问题导入
这道题直接使用遍历,效率太差,不推荐使用;
第二种方法就是先排序+二分查找:肯呢个有些人会觉得,排序的代价太大了;其实不然,我们只需要排序一次那么接下来的查找就好办了;
对于二分查找,效率是O(logn),根据2^10=1024,那2^30的数量级就是10^9,就已经上升到亿了,2^32大约就是40亿;所以我们使用二分在40亿个数中查找一个数最多只需要查找32次就可以了,效率是相当客观的;
那么问题来了:我们排序的数据是在内存中的,但是我们能在内存中直接开出40亿个整形吗?来计算一下;
答案肯定是不行的;1GB=1024MB=1024*1024KB=1024*1024*1024B(B是字节),10^9量级大约等于10亿多字节;一个整形4字节,40亿个整形就是16*10^9字节,相当于是16亿G;
所以40亿个整数是无法直接放到内存中的,只能放到硬件文件中,而二分查找只能堆内存中的数组中的有序数据进行查找;
针对上述的空间问题,我们可以使用位图思想来实现;
二.什么是位图?
我们都知道一个字节占8个比特位,每个比特位上储存的是二进制数0和1,那我们就可以在每个比特位上根据1或0,来判断是否存在一个数;
2.1如何确定目标数在哪个比特位?
这个问题其实并不难,我们采用无符号整形构造位图,一个整形占4字节,也就是32个比特位,那这样一个整形中我就可以标记32个数;
那如果我要标记35呢?
第一个整形可以标记的数是0-31,第二个整形可以标记的数是31-63......通过观察我们可以得到结论:35在第二个整形中,在第4个比特位也就是下标为3;
结论:N在第N/32个整形中,所在比特位的下标为N%32;
2.2如何存放高低位
我们都知道二进制数排列是从低位向高位的,而按位左移也是从低位向高位的;
同样的在位图中每个整形的存储方式也是如此;那么我们可以推断数值在位图中存储形态;
我们来分析一下:
首先,我要标记一个数1,这个数在第1个整形中,所占比特位下标为1;然后我们在看看2是在哪里标记的;2同样在第一个整形中,比特位下标为2,我们来看比特位高低位分布,2是不是在1的左边;
在一个数的比特位中,高位数的值大于低位数的值; 所以左边存储的是较大的数;右边存储的是较小的数;
2.3位图模拟代码实现
我们先来把整体框架来实现一下:
template <size_t N>//非类型模板参数N:一共有多少个数
class bitset
{
public:bitset():_bs(ceil(N/32.0))//根据模版的N开整形空间{}void set(int n);//标记数void reset(int n);//重置标记bool test(int n);//检查该数是否标记private:vector<int>_bs; //使用变长数组模拟
};2.3.1如何标记一个数
现在如果我们要标记一个数,那我们需要先确定这个数在第几个整形中和第几个比特位;i是所在整形的下标,j是所在比特位的下标:
i=N/32;
j=N%32;
我们通常是将1左移j位然后或上_bs[i];
template <size_t N>//非类型模板参数N:一共有多少个数
class bitset
{
public:bitset():_bs(ceil(N/32.0))//根据模版的N开整形空间:(ceil是向上取整){}void set(int n)
{int i = n / 32;//找到所在整形的下标int j = n % 32;//找到所在整形中对应的比特位_bs[i] |= 1 << j;
}void reset(int n);bool test(int n);//检查该数是否标记private:vector<int>_bs; //使用变长数组模拟
};2.3.2如何重置标记
我们只需要将该比特位&上~(1<<j)即可;
template <size_t N>//非类型模板参数N:一共有多少个数
class bitset
{
public:bitset():_bs(ceil(N/32.0))//根据模版的N开整形空间:(ceil是向上取整){}void set(int n)
{int i = n / 32;//找到所在整形的下标int j = n % 32;//找到所在整形中对应的比特位_bs[i] |= 1 << j;
}void reset(int n)
{int i = n / 32;//找到所在整形的下标int j = n % 32;//找到所在整形中对应的比特位_bs[i] &= ~(1 << j);
}bool test(int n);//检查该数是否标记private:vector<int>_bs; //使用变长数组模拟
};2.3.3如何检查一个数是否被标记
判断一个比特位是否是1:将该比特位&1,如果是1那就是1,如果是0那就是0;
template <size_t N>//非类型模板参数N:一共有多少个数
class bitset
{
public:bitset():_bs(ceil(N/32.0))//根据模版的N开整形空间:(ceil是向上取整){}void set(int n)
{int i = n / 32;//找到所在整形的下标int j = n % 32;//找到所在整形中对应的比特位_bs[i] |= 1 << j;
}void reset(int n)
{int i = n / 32;//找到所在整形的下标int j = n % 32;//找到所在整形中对应的比特位_bs[i] &= ~(1 << j);
}bool test(int n){int i = n / 32;//找到所在整形的下标int j = n % 32;//找到所在整形中对应的比特位return _bs[i] & (1 << j); }private:vector<int>_bs; //使用变长数组模拟
};整体代码实现
#include<iostream>
#include<vector>
#include<Bitset>
using namespace std;
namespace bit {template <size_t T>class bitset{public:bitset():_bs(ceil(T/32.0)){}void set(int n){int i = n / 32;//找到所在整形的下标int j = n % 32;//找到所在整形中对应的比特位_bs[i] |= 1 << j;}void reset(int n){int i = n / 32;//找到所在整形的下标int j = n % 32;//找到所在整形中对应的比特位_bs[i] &= ~(1 << j); }bool test(int n){int i = n / 32;//找到所在整形的下标int j = n % 32;//找到所在整形中对应的比特位return _bs[i] & (1 << j); }private:vector<int>_bs; };
}标准库的Bitset
其中最核心的就是set和reset;其他的了解即可;
库中的bitset的缺陷
我们模拟实现的bitset底层是使用的vector,而vector的空间来自堆上;这就意味着,我们开一个比较大的空间时bitset的大小是不变的;一直都是vector<int>的大小;
我们来验证一下:
结果一直都是32;为什么是32呢;根据我们在前面Vector的模拟实现可以得知,32是多个指针所占的内存空间;
那标准库中的bitset是什么样的呢?
标准库中的bitset底层是使用静态数组实现的;那么这就意味着空间是在堆栈上开辟的;其实堆栈是很小的,所以当我们开出一块很大的空间的时候容易出现问题;
所以当数据量十分巨大的时候我们尽量使用自己构造的bitset;
另外就是当我们使用我们的bitset<-1>bs时,是可以开出很大的空间的;
但是库中的bitset不支持此操作;
简单应用
这道题是有100亿个数,并且要统计次数,有效的次数就是0,1,2,3;正好占2个比特位,可以使用两个比特位来表示出现的次数;
这道题就是要是使用两个位图协同进行标记;
具体思路:封装两个位图->twoset,底层是bitset<1e10>bs1,bitset<1e10>bs2;分别代表n出现次数的两个比特位;
代码实现:
#include<iostream>
#include<vector>
#include<Bitset>
using namespace std;
namespace bit
{template <size_t N> class bitset{public:bitset():_bs(ceil(N/32.0)) {}void set(int n){int i = n / 32;//找到所在整形的下标int j = n % 32;//找到所在整形中对应的比特位_bs[i] |= 1 << j;}void reset(int n){int i = n / 32;//找到所在整形的下标int j = n % 32;//找到所在整形中对应的比特位_bs[i] &= ~(1 << j); }bool test(int n){int i = n / 32;//找到所在整形的下标int j = n % 32;//找到所在整形中对应的比特位return _bs[i] & (1 << j); }private:vector<int>_bs; };template <size_t T>class twoset{public:twoset() = default;void set(size_t n){//00->01if (!bs1.test(n) && !bs2.test(n)){bs2.set(n);}else if (!bs1.test(n) && bs2.test(n))//01->10{bs1.set(n);bs2.reset(n);}else//10->11{bs2.set(n);}}int get_count(int n){return bs1.test(n)*2 + bs2.test(n);}private:bitset<T>bs1; bitset<T>bs2; };}
