C++实现位图

2023-12-21 19:41:37

目录

一、什么是位图

二、位图类

1.参数及构造函数

2.set函数设置为1(代表存在)?

3.reset函数设置为0(代表不存在)

4.test函数查看状态(0还是1)

三、位图的变形


一、什么是位图

位图这个词汇比较少见,在学习位图之前,我们可以先来看看下面这个问题

40亿个数,大约为2^32。 这里有几个方案解决

解决方案1:暴力查找,将数据遍历一遍直到找到,但是40亿个数据太大了,如果换算为整数,那么至少需要16G(4*2^32代表4个字节,再乘以个数)的内存,一般的电脑是没办法开辟出这么大的连续空间的。

解决方案2:就是已经是有序了我们只需二分查找,二分查找的效率为log(n),但这里跟效率没啥关系,主要还是无法开辟这么大的内存的问题

解决方案3:将数据放到unordered_set或者set中,使用哈希表和红黑树的思想帮我们查找,但是哈希表和红黑树他们存放的结点会占用更多的空间,因为存放的结点不仅仅有数据,还有指针,因此更无法使用。

前面的几个解决方案都没有办法解决这种较大数据的问题,那么我们引入概念位图。

每一个值映射一个bit位,那么我们只需要一个bit位就可以知道该位置的值是否存在了,0为不存在,1为存在。这就叫做位图。

那么40亿个数据按照这种方法来表示他们是否存在的状态,只需要0.5G(2^32/8 代表所有的数据除以每个字节的8位)

二、位图类

其实库里面也有bitset位图,我们模仿一下这个位图的基本函数。

1.参数及构造函数

我们写出一个类,类的模板参数只有一个常量,代表我们要存放多少个数据的状态(bit位),类成员为vector<int> _bits;?

同时构造参数是给_bits开辟足够的空间,_bits.resize(N / 32 + 1, 0);? ?N/32代表一个整形的每一个bit位都存放状态,+1是为了防止除数把余数丢掉,比如40/32==1,如果我们只开辟一个int整形,就会将后面的数据丢掉。

template<size_t N>
class bitset
{
public:
	bitset()
	{
		_bits.resize(N / 32 + 1, 0);
	}
private:
    vector<int> _bits;
}

2.set函数设置为1(代表存在)?

?有了这个,我们如何来设置,让我们想要映射的位置变为1呢?

首先,参数部分肯定需要一个整数,代表是这个数据,我们可以通过 x/32 来表示映射到哪一个整形里了,再通过 x%32来表示映射该整形的哪一个bit位。这样我们就可以找到映射的位置了,找到位置后,应该如何将他的值赋为1呢?

我们的想法是让他无论是为0还是为1,我都要设置为1,这样初步会考虑到 |(或运算),肯定是 | 上1,我们可以通过左移运算符,将1左移到想要的位置,也就是 j?位置。这样进行或运算,就可以保证在不影响其他位置的值的前提,将想要的位置置为1了

代码如下?

void set(size_t x)
{
	int i = x / 32;
	int j = x % 32;
	_bits[i] |= (1 << j);
}

3.reset函数设置为0(代表不存在)

有了设置存在,我们也得设置不存在,如何操作呢?

一样的方法先找到 i 和 j ,无论该值为1还是为0,要想设置为0,就需要&(与运算)0才行那我们将 1 左移 j 位,再取反,就让想要的bit位变成了0,其他位都为1。

任何数(指0和1)与上1都是他本身,这样就没有改变其他bit位,任何数与上0都为0,这样就达到我们的设置改bit位为 0 目的了。

代码如下?

void reset(size_t x)
{
	int i = x / 32;
	int j = x % 32;
	_bits[i] &= ~(1 << j);
}

4.test函数查看状态(0还是1)

?有了置为1和置为0,我们还需要去查看该位置的状态。

依然是计算出? i? 和? j? ,与上(1<<j)返回即可,因为任何数(指0和1)与上1都是他本身,因此我们状态为0就返回0,为1就返回1,就知道该位置的状态了。

bool test(size_t x)
{
	int i = x / 32;
	int j = x % 32;
	return _bits[i] & (1 << j);
}

测试一下,没有问题,这样就极大的节省了空间。

三、位图的变形

?如下面这个题,就是位图的变形题。

?这里也有两个方案去解决。

方案1:将单位图修改为双位图,从整形存放32个状态(0或1),编程存放16个(00或01或10)状态。由于找到只出现一次的整数,那么状态我们只需要设置(00或01或10)分别代表0个、1个、2个及以上。这个方案虽然可行,但是要重新修改位图,比较麻烦。

方案2:再写一个类,变量为两个位图,第一个位图代表状态(00或01或10)的前一个bit位,第二个位图代表状态(00或01或10)的后一个bit位

很明显,代码复用要香很多,我们选择方案2。

?set函数中,如果bit1的test(x)为false,bit2的test(x)也为false,那么就将bit2的该位置设置为1。

如果bit1的test(x)为false,bit2的test(x)为true,就将bit1位置设置为1,bit2位置设置为0,就完成了。

再写一个打印函数就完成了。

具体代码如下

template<size_t N>
class twobitset
{
public:
	void set(size_t x)
	{
		if (bit1.test(x) == false && bit2.test(x) == false)
		{
			bit2.set(x);
		}
		else if (bit1.test(x) == false && bit2.test(x) == true)
		{
			bit1.set(x);
			bit2.reset(x);
		}
	}
	void PrintOnce()
	{
		for (size_t i = 0; i < N; i++)
		{
			if (bit1.test(i) == false && bit2.test(i) == true)
			{
				cout << i << endl;
			}
		}
		cout << endl;
	}
private:
	bitset<N> bit1;
	bitset<N> bit2;
};

代码测试,没问题。

该位图只涉及到了整数的处理,如果是字符串怎么处理呢?需要用到布隆过滤器,这个我们下次再讲。

最后附上总代码

bitset.h

#pragma once
#include<vector>
namespace kky
{
	template<size_t N>
	class bitset
	{
	public:
		bitset()
		{
			_bits.resize(N / 32 + 1, 0);
		}
		void set(size_t x)
		{
			int i = x / 32;
			int j = x % 32;
			_bits[i] |= (1 << j);
		}

		void reset(size_t x)
		{
			int i = x / 32;
			int j = x % 32;
			_bits[i] &= ~(1 << j);
		}

		bool test(size_t x)
		{
			int i = x / 32;
			int j = x % 32;
			return _bits[i] & (1 << j);
		}

	private:
		vector<int> _bits;
	};
	template<size_t N>
	class twobitset
	{
	public:
		void set(size_t x)
		{
			if (bit1.test(x) == false && bit2.test(x) == false)
			{
				bit2.set(x);
			}
			else if (bit1.test(x) == false && bit2.test(x) == true)
			{
				bit1.set(x);
				bit2.reset(x);
			}
		}
		void PrintOnce()
		{
			for (size_t i = 0; i < N; i++)
			{
				if (bit1.test(i) == false && bit2.test(i) == true)
				{
					cout << i << endl;
				}
			}
			cout << endl;
		}
	private:
		bitset<N> bit1;
		bitset<N> bit2;
	};
}

?test.cpp

#include<iostream>
using namespace std;
#include"bitset.h"
//int main()
//{
//	kky::bitset<100> bs;
//	bs.set(10);
//	bs.set(11);
//	
//	cout << bs.test(9) << endl;
//	cout << bs.test(10) << endl;
//	cout << bs.test(11) << endl;
//	cout << bs.test(12) << endl;
//	bs.reset(10);
//	cout << bs.test(10) << endl;
//}




int main()
{
	int a[] = { 1,3,4,6,8,4,6,3,1,5,7 };
	kky::twobitset<100> bs;
	for (auto e : a)
	{
		bs.set(e);
	}
	bs.PrintOnce();
}

谢谢大家观看!!!?

文章来源:https://blog.csdn.net/kkbca/article/details/135134866
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。