C++位图简明介绍与实现

Cola_Forever

已于 2022-08-14 08:45:59 修改

阅读量694

点赞数

文章标签： c++ 算法

于 2022-08-13 19:47:37 首次发布

本文链接： https://blog.csdn.net/jiaao666/article/details/126322948

版权

本文介绍了如何使用C++的位图数据结构解决大数据问题，如快速判断一个数是否在40亿个整数中，以及设计算法找到只出现一次的整数、在有限内存下找到文件交集和出现次数不超过两次的整数。位图通过使用bitset库提供高效解决方案。

摘要由CSDN通过智能技术生成

何时使用位图？

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

遍历，时间复杂度O(N)
排序(O(NlogN))，利用二分查找: logN
上述两种方法都不是很好，因此有了位图的用武之地

位图（表示一个数在不在）

数据是否在给定的整形数据中，结果是在或者不在，刚好是两种状态，那么可以使用一个二进制比特位来代表数据是否存在的信息，如果二进制比特位为1，代表存在，为0代表不存在。比如：

用位图解决上述问题需要的空间为：

因此位图需要开42亿9千万个比特即500M的空间：

位图的简单实现（C++库中有：bitset）

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


namespace cola
{
   
	template<size_t N>
	class bitset
	{
   
	public:
		bitset()
		{
   
			//假设为7：7/8 = 0或10：10/8 = 1，因此最后加一个1防止空间不够用
			_bits.resize(N / 8 + 1, 0);//初始化为全0
		}

		//将数据存入位图
		void set(size_t x)
		{
   
			//计算x会放到第几个字节
			size_t i = x / 8;

			//计算x会放到第几位
			size_t j = x % 8;

			//存入位图中（位图置为1）
			_bits[i] |= (1 << j);
		}

		//将数据从位图中移除
		void reset(size_t x)
		{
   
			//计算在第几个字节
			size_t i = x / 8;

			//计算第几位
			size_t j = x % 8;

			//将数据移除（位图置为0）
			_bits[i] &= ~(1 << j);
		}

		//查看数据是否存在（位图是否为1）
		bool test