【C++】位图+布隆过滤器

1.位图

概念

所谓位图，就是用每一位来存放某种状态，适用于海量数据，数据无重复的场景。通常是用来判断某个数据存不存在的或是否被标记。

1.二进制位表示 ：

位图中的每一位（bit）代表一个元素的状态。通常，1 表示元素存在或被标记，0 表示元素不存在或未被标记。

2.空间高效性 ：

每个元素仅占用 1 比特的空间，相比其他数据结构存储数据最小也只是char类型占1字节8比特位，可见位图在存储空间上极为高效.

问题引入

面试题：

给40亿个不重复的无符号整数，没排过序。给一个无符号整数，如何快速判断一个数是否在这40亿个数中。

分析：

1G

=1024MB

=1024x1024KB

=1024x 1024x1024Byte

=2^30Byte=10亿+Byte

40亿整数等于160亿Byte，约等于16个G左右

set等数据结构和排序方法不适用

因为内存占用过大，插入查找效率不高

运用位图解决：

位图用1位表示每个可能的整数是否存在。无符号整数范围是0到4,294,967,295个可能的值，位图需要约512MB内存（4,294,967,296位 ÷ 8 = 512MB），远小于 set 的内存需求，内存空间只需原来的1/8。

位图的查找操作是O(1)时间复杂度，通过简单的位运算即可判断一个数是否存在。

1.2位图的实现

复习位运算

基本操作：

1.与运算（AND） ：符号为 &

用于比较两个二进制数的每一位。只有当两个数的对应位都是1时，结果位才是1，否则为0。

2.或运算（OR） ：符号为 |

比较两个二进制数的每一位。只要两个数的对应位中有一个是1，结果位就是1，否则为0。

3.异或运算（XOR） ：符号为 ^

比较两个二进制数的每一位。只有当两个数的对应位不同时，结果位才是1，否则为0。

4.取反运算（NOT） ：符号为 ~

对一个二进制数的每一位取反。即把1变为0，0变为1。

5.左移运算（Left Shift） ：符号为

将一个二进制数的各位向右移动指定的位数。右边溢出的位被丢弃，左边空出的位用0填充（对于无符号数）或用符号位填充（对于有符号数）。

注意：左移是往高地址，右移往低地址，不是指方向

位运算的应用：

数据压缩 ：通过位运算可以将多个布尔值或小整数打包到一个较大的数据类型中，从而节省空间。

标记状态 ：使用位图来标记状态，如文件系统的磁盘块使用情况、内存管理中的页面使用情况等。

高效计算 ：位运算在某些数学计算中非常高效，比如乘以或除以2的幂次时，可以用左移或右移运算代替乘法或除法。

并发编程 ：在原子操作中，位运算可以用于实现锁和标志位等。

位运算的优势:

性能高效 ：位运算在计算机底层硬件层面直接操作二进制位，通常比其他算术运算更快。

空间节省 ：可以用较少的空间存储大量的二进制状态信息，如位图。

实现

• bitset类模板

  namespace ee
  {
  	template
  	class bitset
  	{
  	public:
  		bitset()
  		{
  			_a.resize(N / 32 + 1);
  		}
  	private:
  		vector _a;
  	};
  }
  

  1.N 是一个非类型模板参数，是无符号整型，表示位集合中位的数量。

  2.构造函数中，N / 32 计算出需要的完整整数数量。如果 N 不是32的倍数，则 N / 32 会向下取整，因此需要加1来确保有足够的空间存储所有位。最坏的情况是刚好整除，多了32个比特位

  3.用vector _a;来存储位集合，每个集合可存储8个比特位

  注意：位图开空间看的是数据的范围而不是个数，对于连续稠密的数据处理来说空间利用率很高效，处理稀疏数据可以采取哈希表或布隆过滤器等其他数据结构

  • 设置位状态

    void set(size_t x)
    {
    	size_t i = x / 32;
    	size_t j = x % 32;
    	_a[i] |= (1 
    	size_t i = x / 32;
    	size_t j = x % 32;
    	_a[i] &=( ~(1 
    	size_t i = x / 32;
    	size_t j = x % 32;
    	return _a[i] &(1 
    	int a1[] = { -1,2,3,3,4,4,4,4,4,2,3,6,3,1,5,5,8,9 };
    	int a2[] = { -1,8,4,8,4,1,1,1,1 };
    	ee::bitset
    		bs1.set(e);
    	}
    	// 去重
    	for (auto e : a2)
    	{
    		bs2.set(e);
    	}
    	size_t x = -1;
    	cout 
    		if (bs1.test(i) && bs2.test(i))
    		{
    			cout 
    public:
    public:
    	void set(size_t x)
    	{
    		//将位状态00标记为01
    		if (!_bs1.test(x) && !_bs2.test(x))
    		{
    			_bs2.set(x);
    		}//01-10
    		else if (!_bs1.test(x) && _bs2.test(x))
    		{
    			_bs1.set(x);
    			_bs2.reset(x);
    		}
    		//10代表两次以上，不用变了
    	}
    	bool is_once(size_t x)
    	{
    		//返回标记状态为01的位
    		return !_bs1.test(x) && _bs2.test(x);
    	}
    private:
    	bitset
    	int a[] = { 1,2,3,3,4,4,4,4,4,2,3,6,3,1,5,5,8,9 };
    	ee::twobitset
    		tbs.set(e);
    	}
    	//遍历查找位状态位01的数据
    	for (auto e : a)
    	{
    		if (tbs.is_once(e))
    		{
    			cout 
    	int a1[] = { 1,2,3,3,4,4,4,4,4,2,3,6,3,1,5,5,8,9 };
    	int a2[] = { 8,4,8,4,1,1,1,1 };
    	ee::bitset
    		bs1.set(e);
    	}
    	// 去重
    	for (auto e : a2)
    	{
    		bs2.set(e);
    	}
    	//寻找交集
    	for (int i = 0; i