1. 位图简介

• 位图：

  就是以每一个来表示存放的状态，适用于面对海量数据的数据无重复的场景。通常是用来判断某个数据存不存在的……

例：现在有40亿个不重复的无符号整型数据，没有排过序，如何判断一个数是否在这40亿数据中出现过？

• 思路：

  1. 方案一：set去重。效率为O($lo{g}_{2}N$)。

  2. 方案二：排序 + 二分查找。效率为O($lo{g}_{2}N$)。

     上面两个方案都有一个严重的问题：面对40亿的整型数据，我们一定是需要先将这些数据先存储再进行操作。而内存是万万不够的！！！
     一个整型我们算4Byte，40亿就是：160亿Byte。 1G = 1024 * 1024 * 1024Byte = 10亿Byte+
     所以如果我们需要将所有的数据先存储就需要16G的内存！！

  3. 方案三：位图。

     因为我们只判断某个数据在不在，所以我们需要要用一个bit位0/1来表示一个数据是否存在！开辟一段连续的空间，起始bit位我们标记为0代表对应的数据大小，而对应的bit为的内容为0/1代表该数据是否存在！

     • 优势：之前4个Byte一共有32bit位，之前只存储一个数据，现在能判断32个数据！

     • 体现：之前需要16G的内存现在可以缩减到，0.5G ≈ 512MB。

     • 注意：我们位图开辟的空间，是以范围大小来看，不是数据多少！例如，上面的40以无符号整型数据来说，我们开辟的空间大小应该是$2^{32}$ ≈ 42亿+包含所有的范围。

       为了方便计算，我们利用int类型的4个Byte来计算。开辟的空间以32bit为一个单位！

2. 位图的操作（模拟）

• 对于位图常见的操作：

  1. set：设置某个位置为1。
  2. unset：设置某个位置为0。
  3. check：检查某个位置是否存在。

• 关于下面的位图的操作，我们主要是位运算。关键点在于：

  1. 在第几个整型？
  2. 在第几个bit位？

  这两个问题我们可以通过/(除法)、%(取模)运算来解决。

下面给出代码：

#pragma once
#include<iostream>
#include<vector>
using namespace std;

namespace LL
{
	template<size_t N>
	class bitset
	{
	public:
		bitset()
		{
			//1个整型4个字节，32个bit位
			//向上取整
			_a.resize(N / 32 + 1);
		}

		void set(size_t n)
		{
			int i = n / 32; //算出在第几个int
			int j = n % 32; //算出在i个int的第几个位置
			_a[i] |= (1 << j);
		}

		void unset(size_t n)
		{
			int i = n / 32;
			int j = n % 32;
			_a[i] &= (~(1 << j));
		}

		bool check(size_t n)
		{
			int i = n / 32;
			int j = n % 32;
			return _a[i] & (1 << j);
		}
	private:
		vector<int> _a;
	};
}

3. 位图的运用

1. 问题一：给定100亿个整型数据，如何设计算法找到只出现一次的正数？

   • 分析：

     我们发现100亿的数据量肯定是无法正常存储的，既然要求我们只判断在不在。我们就可以利用位图来进行判断。可是由于我们的单个位图只能判断是否出现。所以单个位图是无法解决问题的，所以我们可以利用两个位图来解决问题。
     两个位图（一个表示高位，一个表示低位）的排列有四种情况：00 01 10 11
     00：表示没有出现
     01：表示出现一次
     10：表示出现两次
     11：表示出现三次及以上

用代码体现：

template<size_t N>
class twobitset
{
public:
	void set(size_t n)
	{
		if (!_a1.check(n) && !_a2.check(n)) // 00—>01
		{
			_a2.set(n);
		}
		else if (!_a1.check(n) && _a2.check(n)) //01->10
		{
			_a1.set(n);
			_a1.unset(n);
		}
		//其余就不再管
	}
	bool is_once(size_t n)
	{
		return !_a1.check(n) && _a2.check(n);
	}
private:
	bitset<N> _a1; //高位
	bitset<N> _a2; //低位
};

• 同时上面的这种思路还可以用于找到次数不超过2的数字。

2. 问题二：给定两个文件，分别用100亿个正数，我们只有1G内存，如何找到两个文件的交集？

   • 第一种：将一个文件的内容映射到一个位图中，然后再判断另外一个文件中的数据是否在位图中！但是最后的结果需要注意：我们需要对最后的结果进行去重，因为我们判断另一个文件是否存在的时候无法判断之前是否已经判断过了。
   • 第二种：两个文件的数据分别放入两个位图中，然后做&运算，为1的就是交集。

完。希望这篇文章能够帮助你！！