【C++】位图

青衫哥

发布于 2023-04-24 11:39:08

3300

发布于 2023-04-24 11:39:08

文章被收录于专栏：C++打怪之路

前言

我们先来看腾讯曾经的一道面试题： 给40亿个不重复的无符号整数，没排过序。给一个无符号整数，如何快速判断一个数是否在 这40亿个数中。 常规方法： 1. 遍历，时间复杂度 O(N) 2. 排序 (O(NlogN)) ，利用二分查找 : logN 这道题如果是不可能用常规方法来解决的，因为存储40亿个整形需要的空间太大了，高达16G。这种情况，我们就可以用到今天的主角—— 位图。给定的每个整形只有两种状态：在与不在，我们完全可以通过一个比特位的0和1来记录每个数字在不在。这样大大节省了空间，只需要500MB的空间即可。

一、概念

所谓位图，就是用每一位来存放某种状态，适用于海量数据，数据无重复的场景。通常是用

来判断某个数据存不存在的。

二、代码实现

底层结构我们用一个vector，容器中存储的类型为char。因为一个char类型占用一个字节，我们将八个比特位（一个字节）分为一个区间。

1.set

功能：将给定的数字对应的比特位数字标记为1。

关于数字的位置：我们怎么确定一个数字在第几个字节的第几个比特位呢？其实很简单，因为一个字节是八个比特位的大小，所以数字的字节位置 = 数字 / 8，数字的比特位位置 = 数字 % 8。我们知道，0和1或上一个1，那么该位都为1。所以我们只需要把对应的位置或上1即可。

代码：

void set(size_t x)
{
	//i表示在第几个字节,j表示在第几个比特位
	size_t i = x / 8;
	size_t j = x % 8;

	_bits[i] |= (1 << j);
}

2.reset

功能：将给定的数字对应的比特位数字标记为0。

如何做到保证其他位数字不变，特定位置的数字置零呢？ 0和1与1都等于它本身，而0和1与0都等于0，所以我们只需要其他位与1，而对应的位置与0，即可做到置零。

void reset(size_t x)
{
	size_t i = x / 8;
	size_t j = x % 8;

	//与上的数字其他位都是1,为了让其他位保持不变
	//需要reset的位置与上0,为了让其置零
	_bits[i] &= (~(1 << j));
}

3.test

功能：判定给定的数字对应的比特位数字是否为1。

只需要该位与1，如果该位为0，与1后的数字为0。该位为1，与1后的数字不为零。

bool test(size_t x)
{
	size_t i = x / 8;

	size_t j = x % 8;

	return _bits[i] & (1 << j);
}

完整代码：

#pragma once
#include <vector>
namespace BitSet
{
	template<size_t N>
	class bitset
	{
	public:
		bitset()
		{
			//_bits.resize(N / 8 + 1, 0);
			_bits.resize((N >> 3) + 1, 0);
		}

		void set(size_t x)
		{
			//i表示在第几个字节,j表示在第几个比特位
			size_t i = x / 8;
			size_t j = x % 8;

			_bits[i] |= (1 << j);
		}

		void reset(size_t x)
		{
			size_t i = x / 8;
			size_t j = x % 8;

			//与上的数字其他位都是1,为了让其他位保持不变
			//需要reset的位置与上0,为了让其置零
			_bits[i] &= (~(1 << j));
		}

		bool test(size_t x)
		{
			size_t i = x / 8;

			size_t j = x % 8;

			return _bits[i] & (1 << j);
		}


	private:
		vector<char> _bits;
	};

}

三、位图的应用

1. 快速查找某个数据是否在一个集合中 2. 排序 + 去重 3. 求两个集合的交集、并集等 4. 操作系统中磁盘块标记

面试题：

1. 给定100亿个整数，设计算法找到只出现一次的整数？

一个数字有三种状态：0次、1次、超过一次。所以我们需要用两个比特位来记录。由于用连续的两个比特位来记录会比较麻烦，我们可以开两个位图，各用一位来记录高位和地位。

这样就能复用我们的bitset了。

代码：

template<size_t N>
	class twobitset
	{
	public:
		void set(size_t x)
		{
			if (!_bs1.test(x) && !_bs2.test(x)) //00
			{
				_bs2.set(x);
			}
			else if (!_bs1.test(x) && _bs2.test(x))	//01
			{
				_bs1.set(x);
				_bs2.reset(x);
			}
			//10不需要管

		}
		void PrintOnce()
		{
			for (size_t i = 0; i < N; ++i)
			{
				if (!_bs1.test(i) && _bs2.test(i))
				{
					cout << i << endl;
				}
			}
		}


	private:
		bitset<N> _bs1;
		bitset<N> _bs2;
	};

}

2. 给两个文件，分别有100亿个整数，我们只有1G内存，如何找到两个文件交集？