写点什么

C++ 语法中 bitset 位图介绍及模拟实现

作者:向阳逐梦
  • 2023-08-12
    四川
  • 本文字数:1719 字

    阅读完需:约 6 分钟

C++语法中bitset位图介绍及模拟实现

一、位图的引入

先来看下边一道面试题:

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

经过我们之前的学习,我们可能会有以下的思路:

  • 对这些数进行排序,再通过二分算法,查找这个数是否存在

  • 插入到 unordered_set 中,使用 find 函数查找是否存在

上述方法看起来还不错,二分查找算法时间复杂度为 logN,而插入到 unordered_set 中时间复杂度为 O(N),而查找时时间复杂度为 O(1),但是都有一个问题就是要将空间不足,40 亿个无符号整形,需要 160 亿字节的空间,大概就是 16GB 的空间,一般计算机的内促都是 4G 或者 8G,所以空间不足,此时就有了位图的方法来解决:

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

对于上图来说,有一个整形数组,我们可以使用直接定址法对数组的数据进行映射,但是与之前不同的是,此时只是使用一个比特位来代表一个整形数据,当这个数存在时,比特位置 1,不存在时,比特位置 0,此时就可以大大节省空间资源,无符号整数只有 2 的 32 次方个,所以最多开 2 的 32 次方个空间,一个空间为一个比特,所以最终只需要 512MB 的空间。但是我们不能按照位来空间,最少必须一个字节,所以我们就每次开一个字节的空间,也就是 8 个比特位,将 8 位当做一个整体来处理,对要保存的数据除 8 就是第几个字节,对保存的数据模 8 就是在这个字节中的第几个位置。

二、位图的概念

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

那么位图还有哪些应用呢?

  • 快速查找某个数据是否在一个集合中

  • 排序 + 去重

  • 求两个集合的交集、并集等

  • 操作系统中磁盘块标记

位图模拟实现

一、构造函数

由于不能按位开空间,所以我们选择每次开一个字节的空间,由于有范围最大为 N,一位关联一个数据,所以需要开 N/8 个字节的空间,但是有时可能不能整除,所以要开 N/8+1 个字节的空间。所以

直接在构造函数中开好空间:

bitset()		{			_bits.resize(N / 8 + 1,0);		}
复制代码

二、set,reset,test 函数

set 函数的作用是对位图中的某一位进行填充

i 就表示是第几个字节,而 j 表示该位在该字节中的第几位,所以对 1 进行左移 j 位后与该字节按位或,按位或的作用时不论该位为 0 还是为 1,都将该位变为 1。


void set(size_t x)		{			int i = x / 8;			int j = x % 8;			_bits[i] |= (1 << j);		}
复制代码

reset 的作用是将某一位清空

同样的将要清空的那一位置为 0,进行按位与,不论原本该位是 0 还是 1,都将该位置 0


void reset(size_t x)		{			int i = x / 8;			int j = x % 8;			_bits[i] &= ~(1 << j);		}
复制代码

test 的作用是检测位图中某一位是否存在


bool test(size_t x)		{			int i = x / 8;			int j = x % 8;			return _bits[i] & (1 << j);		}
复制代码

三、代码测试

void test_bit_set1()	{		bitset<100> bs1;		bs1.set(8);		bs1.set(9);		bs1.set(20);		cout << bs1.test(8) << endl;		cout << bs1.test(9) << endl;		cout << bs1.test(20) << endl;		bs1.reset(8);		bs1.reset(9);		bs1.reset(20);		cout << bs1.test(8) << endl;		cout << bs1.test(9) << endl;		cout << bs1.test(20) << endl;	}
复制代码


四、完整代码

namespace tmt{	template<size_t N>	class bitset	{	public:		bitset()		{			_bits.resize(N / 8 + 1,0);		}		void set(size_t x)		{			int i = x / 8;			int j = x % 8;			_bits[i] |= (1 << j);		}		void reset(size_t x)		{			int i = x / 8;			int j = x % 8;			_bits[i] &= ~(1 << j);		}		bool test(size_t x)		{			int i = x / 8;			int j = x % 8;			return _bits[i] & (1 << j);		}	private:		vector<char> _bits;	};	void test_bit_set1()	{		bitset<100> bs1;		bs1.set(8);		bs1.set(9);		bs1.set(20);		cout << bs1.test(8) << endl;		cout << bs1.test(9) << endl;		cout << bs1.test(20) << endl;		bs1.reset(8);		bs1.reset(9);		bs1.reset(20);		cout << bs1.test(8) << endl;		cout << bs1.test(9) << endl;		cout << bs1.test(20) << endl;	}
复制代码



发布于: 刚刚阅读数: 5
用户头像

向阳逐梦

关注

人生享受编程,编程造就人生! 2022-06-01 加入

某公司芯片测试工程师,嵌入式开发工程师,InfoQ签约作者,阿里云星级博主,华为云·云享专家。座右铭:向着太阳,追逐梦想!

评论

发布
暂无评论
C++语法中bitset位图介绍及模拟实现_向阳逐梦_InfoQ写作社区