C++位图

文章目录

我们如果要查看100亿个数中某个数是否存在是完全不合理的,内存根本存放不下这么多的数,会爆炸
这样我们就可以用一个bit位来代表一个数
例如一个字节8个bit位,其中如果第2位被设置成1,说明2,这个数存在
这个也是一种映射关系

但是位图只能处理整数,这个就是它最大的问题

bit_set的模拟实现

  • bitset里面的成员对象我们设置为vector里面是char,可以对里面的比特位进行操作
  • 通过计算在第几个char中第几个位里面
  • 运用位运算来进行置1,或置0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#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
}
};

位图的应用

  1. 给定100亿个数,设计算法,找到只出现一次的整数
    思路我们可以使用两个位图,组成00,01,10,11序列

我们只要用这个判断出现的是01即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
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;
}
}
}

};
  1. 给两个文件,分别由100亿个整数,我们只有1G内存,如何找到两个文件的交集
  • 法1:一个文件中的整数,set到一个位图,读取第二个整数是否在一个位图,在就有,不在就没有交集,这个就要用O(N),交集中,会把重复值找出来,多次出现
  • 法2:思路2,读取一个整数设计到位图bs1,再把另一个文件中的整数,set到位图bs2,a.把bs1中的值,一次和bs2中的值进行与一下,再去看,与完是1的位置的值,就是交集,全1是1
  1. 一个文件中100亿个int,1g内存,找到出现次数不超过2次的整数,
    这个方法的思路和上面只出现一次的思路很相似
    但是这次是用3个bit位进行操作

C++位图
http://example.com/2022/10/23/C++位图/
作者
Zevin
发布于
2022年10月23日
许可协议