成都创新互联网站制作重庆分公司

【C++】哈希-bitset位图与模拟-创新互联

目录

创新互联公司是一家专注于成都网站制作、做网站、外贸营销网站建设与策划设计,云龙网站建设哪家好?创新互联公司做网站,专注于网站建设十载,网设计领域的专业建站公司;建站业务涵盖:云龙等地区。云龙做网站价格咨询:028-86922220

1.位图

1.1什么是位图 

1.2位图的作用 

2.bitset应用

2.1bitset构造

2.2bitset成员函数与使用 

3.bitset模拟实现 

构造函数 

set

reset

test

flip

count 

size 

none,any


1.位图

在前文中我们介绍了哈希的一些内容,接下来我们介绍一个新奇的玩意,位图。 

1.1什么是位图 
  • 位图其实就是哈希的变形,同样通过映射来处理数据。
  • 位图本身并不存储数据,而是存储标记通过一个比特位来标记这个数据是否存在,1代表存在,0代表不存在。
  • 位图通常情况下用在数据量庞大,且数据不重复的情景下判断某个数据是否存在。

相比通过上面的介绍,各位还是不知道位图有啥作用。接下来我们说一下位图的作用。

1.2位图的作用 

腾讯出过一个面试题: 给40亿个不重复的无符号整数,没排过序。给一个无符号整数,如何快速判断一个数是否在这40亿个数中。

1整数=4字节=32bit。

40亿个整数 = 160亿个字节
而1GB = 1024MB
1024MB = 1024 * 1024KB
1024 * 1024KB = 1024 * 1024 * 1024B(yte )≈ 10亿字节
综上1GB ≈ 10亿字节
   16GB ≈ 160亿字节

遍历时间复杂度O(N);排序(O(NlogN))利用二分查找: logN;这两种方式除了效率不够高,还有个问题是内存无法完全同时加载40亿个整数需要的16G大小空间。

我们也可以用set容器,但是底层的红黑树存放这么多数据也吃不消所以我们用位图来解决这个问题。

1个整形是32bit位,就比如整数在计算机中以二进制来存储的。而这32个位置上只有0或1,那我们可以让1表示有数据,0表示没存放数据。我们以32比特位表示一个单元。

如果采用这种方法,只需占500M内存就可以:

1G = 2^30Byte ≈ 10亿字节
(2^32 - 1)Byte ≈ 40亿字节 ≈ 4G
1Byte = 8bit
(2^32 - 1)bit = 4G/8 ≈ 500MB

例如:int a[]={2,5,7,19,24,30}

2.bitset应用  2.1bitset构造

位图构造有三种形式,这里我们直接上代码。

void testbitset1()
{
    //1.创建一个16位位图,初始0
	std::bitset<16>foo;  // 创建一个16位位图
    //2.赋值16进制
	std::bitset<16>bar(0xfa2);   //16进制 4002
   //3.用0,1赋值或者string
	std::bitset<16>baz(std::string("0101111001"));
	std::bitset<16>bs1("011010001");
	//foo : 0000000000000000
	//bar : 0000111110100010   4002
	//baz : 0000000101111001
	//bs1 : 0000000011010001
	std::cout<< "foo: "<< foo<< '\n';
	std::cout<< "bar: "<< bar<< '\n';
	std::cout<< "baz: "<< baz<< '\n';
	std::cout<< "bs1: "<< bs1<< '\n';
}
2.2bitset成员函数与使用 
成员函数      功能
set                                     设置指定位或所有位
reset  清空指定位或所有位
test  获取指定位的状态
flip  反转指定位或所有位
count   获取被设置位的个数
size  获取可以容纳的位的个数
any    如果有任何一个位被设置则返回true
none    如果没有位被设置则返回true
all    如果所有位都被设置则返回true

void testbitset2()
{
	std::bitset<16>bs1;
	bs1.set(2);  //0000000000000100
	cout<< bs1<< endl;
	bs1.set(4);
	bs1.set(5);  //0000000000110100
	cout<< bs1<< endl;
	//获取指定位置的状态
	cout<< bs1.test(5)<< endl;  //位置5的状态是1
	cout<< bs1.test(10)<< endl; //位置10的状态是0
	//反转
	cout<< bs1.flip(4)<< endl;   //反转第4位
	cout<< bs1.flip()<< endl;    //反转所有位
	//清空
	cout<< bs1.reset(10)<< endl;   //清空第10位
	cout<< bs1.reset()<

bitset运算符那个就不讲了。我们直接模拟实现一下。

3.bitset模拟实现 
  • 模拟bitset就是用一个普通的数组来存储数据以达到模拟的目的。
  • 一个单元我们分成4个小组,每个小组8个位置。存放一个数据要先判断在那个单元,然后是那个小组,那个位置。
  • 找到对应单元后,数据/8=对应小组;数据%8=对应位置。
  • 如果我们以一个整型作为比特位的容器,那么如果要求0~N范围的比特位,就需要有N/32+1个整型来容纳这些比特位,同理如果以char为容器,则需要N/8+1个char来容纳N个比特位。这里我们用vector数组作为底层容纳比特位的容器。之所以+1是怕开的空间存不下,所以多开一个,就算剩下也剩不了多少。
namespace cpp
{
	//N个比特位的位图
	templateclass bitset
	{
	public:
		//构造函数
		bitset();
		//把value映射的位标记成1
		void set(size_t value);
		//把value映射的位标记成0
		void reset(size_t value);
		//判断指定位value的状态是否为1
		bool test(size_t value);
		//翻转指定位置
		void flip(size_t value);
		//获取位图中可以容纳位N的个数
		size_t size()
		//统计set中1的位数
		size_t count();
		//判断所有比特位若无置为1,返回true
		bool none();
		//判断位图中是否有位被置为1,若有则返回true
		bool any();
		//全部NUM个bit位被set返回true
		bool all();
	private:
		vector_bits;//位图
	};
}

这里我们用的存储类型是char。

构造函数 

构造还是构造,但是文章已不是当年的文章了。

public :
		//构造函数
		bit_set
		{
			_bits.resize(N / 8 + 1,0);   // 全部赋值0
		}

之所以+1是因为如果数据的个数不是8的倍数时,可以再存进去,要不那多余的数据咋弄?

set

把映射的位置标记为1(把设置位置标记为1)。

例如:value=13;

//映射的位置标为1
		void set(size_t value)
		{
			size_t i = value / 8;  //找到小组
			size_t j = value % 8;   //找到位置
			//把对应位置标记为1
			_bits[i] |= 1<< j;     //或运算,有1则1
		}
reset

清空指定位或所有位 

这个和set正好相反,这个是把指定位置的数变成0,最后一步变化,其他不变,先按位取反,在按位与即可。j<<1按位取反后变成1,在按位与_bits[i]后就设置成0了。

//把value映射的位标记成0
		void reset(size_t value)
		{
			size_t i = value / 8;  //找到小组
			size_t j = value % 8;   //找到位置
			//把对应位置标记为1
			_bits[i] &=~(( 1<< j));     //先按位取反在与运算
		}
test

判断指定位置是否为1

这个跟上面的reset就缺少一个按位取反。只进行一个按位与运算即可

//判断指定位value的状态是否为1
		bool test(size_t value)
		{
			size_t i = value / 8;  //找到小组
			size_t j = value % 8;   //找到位置
			//把对应位置标记为1
			_bits[i] &= (1<< j);  
		}
flip

指定位置数据翻转: 如果是1变成0,0变成1。

这个按位异或就行了 ,相同为0,1变成0,相异为1,0^1=1

//翻转指定pos
		void flip(size_t value)
		{
			size_t i = value / 8;  //找到小组
			size_t j = value % 8;   //找到位置
			//把对应位置标记为1
			_bits[i] ^= (1<< j);
		}
count 

统计位图中出现的1的次数 

这个跟前面几个就不一样了。

这个是n&n-1

size_t count()
		{
			size_t count = 0;
			for (auto e : _bits)
			{
				int n = e;   //再设置个中间变量,别直接用e
				while (n)
				{
					n = n & (n - 1);
					count++;
				}
			}
			return count;
		}
size 

size的作用是获取位图中可以容纳位N的个数

size_t size()
		{
			return N;
		}
none,any

none是查找位图中是否全部是0,是就返回true,不是返回false。

any是查找位图中是否有1,是就返回true,没有返回false。any可以复用none。完整

bool none()
		{
			//遍历每个char
			for (auto e : _bits)
			{
				if (e != 0)//位图中有位置被置为1,返回false
					return false;
			}
			return true;//说明全为0,返回true
		}
		//若有位置为1,返回true
		bool any()
		{
			 return !none;
		}

完整代码可到gitee查看

C++ 进阶: 本仓库存放一些较难C++代码https://gitee.com/j-jun-jie/c---advanced.git

你是否还在寻找稳定的海外服务器提供商?创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源,准确流量调度确保服务器高可用性,企业级服务器适合批量采购,新人活动首月15元起,快前往官网查看详情吧


当前题目:【C++】哈希-bitset位图与模拟-创新互联
文章路径:http://cxhlcq.cn/article/jjpjd.html

其他资讯

在线咨询

微信咨询

电话咨询

028-86922220(工作日)

18980820575(7×24)

提交需求

返回顶部