文章目录
我们如果要查看100亿个数中某个数是否存在是完全不合理的，内存根本存放不下这么多的数，会爆炸
这样我们就可以用一个bit位来代表一个数
例如一个字节8个bit位，其中如果第2位被设置成1，说明2，这个数存在
这个也是一种映射关系
但是位图只能处理整数，这个就是它最大的问题
bit_set的模拟实现
- bitset里面的成员对象我们设置为vector里面是char，可以对里面的比特位进行操作
- 通过计算在第几个char中第几个位里面
- 运用位运算来进行置1，或置0
#include <vector>
#include "HashTable.hpp"
using namespace std;
#include<bitset>
template <size_t N> //设置开多大的空间,这里的空间，指的是开多少个bit位
class bit_set
{
private:
// vector<int> _bits; //一个字节8个bit位
vector<char> _bits; //
public:
bit_set()
{
_bits.resize(N / 8 + 1, 0); //我们就多浪费一个字节,都初始化成0
}
void set(size_t x) //把对应的x位设置成1
{
//先计算x在第几个char里面
size_t i = x / 8;
//再计算，它再这个的第几个bit位
//直接%就行了
int j = x % 8; //在第j个bit位里面
//直接把它和那个数进行或一下
_bits[i] |= (1 << j); //把这个1左移j位
}
void reset(size_t x) //把对应的x位设置成0
{
//进行按位与
size_t i = x / 8;
int j = x % 8;
_bits[i] &= (~(1 << j)); // 把上面的取反即可
}
bool find(size_t x) //查找一下这个数是存在
{
size_t i = x / 8;
int j = x % 8;
return (bool)_bits[i] & (~(1 << j)); //这样不会改变上面的bits里面的值,如果存在的话就会返回1，不存在就会返回0
}
};
位图的应用
- 给定100亿个数，设计算法，找到只出现一次的整数
思路我们可以使用两个位图，组成00，01，10，11序列
我们只要用这个判断出现的是01即可
template<size_t N>
class twobit
{
//00代表没有
//01代表1个
//10代表2个
private:
bit_set<N> bts1;//左边的0
bit_set<N> bts2;//右边的0
public:
void Set(size_t x)//用两个bit位来表示,上层添加了一个数
{
if(!bts1.find(x)&&!bts2.find(x))
{
//00
bts2.set(x); //第一个0不变，第二个变为1
}
else if (!bts1.find(x)&&bts2.find(x))//已经出现了一次了
{
//01
bts2.reset(x);//第二个变为0
bts1.set(x);//第一变为1
}
else
{
//这个地方就是已经出现了很多次
bts2.set(x);
bts1.reset(x);
}
}
void PrintOnceNum()
{
for(size_t i=0;i<N;i++)
{
if(!bts1.find(i)&&bts2.find(i))
{
//打印是01的数字
//这个就是只出现一次
cout<<i<<endl;
}
}
}
};
- 给两个文件，分别由100亿个整数，我们只有1G内存，如何找到两个文件的交集
- 法1：一个文件中的整数，set到一个位图，读取第二个整数是否在一个位图，在就有，不在就没有交集,这个就要用O（N），交集中，会把重复值找出来，多次出现
- 法2：思路2，读取一个整数设计到位图bs1，再把另一个文件中的整数，set到位图bs2，a.把bs1中的值，一次和bs2中的值进行与一下，再去看，与完是1的位置的值，就是交集,全1是1
- 一个文件中100亿个int，1g内存，找到出现次数不超过2次的整数，
这个方法的思路和上面只出现一次的思路很相似
但是这次是用3个bit位进行操作