当前位置: 首页 > news >正文

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;}

http://www.lryc.cn/news/121078.html

相关文章:

  • Debezium系列之:深入理解消息过滤,实现过滤数据库删除事件,只采集数据库新增和更新事件
  • Substack 如何在去中心化内容创作领域掀起波澜
  • 【MFC】07.MFC六大机制:消息映射-笔记
  • python操作数据库
  • 【C语言】小游戏-三字棋
  • 多线程与并发编程面试题总结
  • 在多页面应用和单页面应用中(例如vue)怎么提高seo搜索引擎优化
  • Dubbo 2.7.0 CompletableFuture 异步
  • pytest-xdist分布式测试原理浅析
  • 研发工程师玩转Kubernetes——PVC通过storageClassName进行延迟绑定
  • 6.利用matlab完成 符号矩阵的秩和 符号方阵的逆矩阵和行列式 (matlab程序)
  • python获取类名__qualname__,解决django接口ObjectDoesNotExist异常寻找model的问题
  • 电流的测量(分流电流表)
  • Leetcode每日一题:23. 合并 K 个升序链表(2023.8.12 C++)
  • 越南的区块链和NFT市场调研
  • MySQL常用语句
  • Mongodb:业务应用(1)
  • 【vue】vue中按钮权限控制:
  • 【博客695】k8s subPathExpr作用
  • 微信小程序中键盘弹起输入框自动跳到键盘上方处理
  • excel将主信息和明细信息整理为多对多(每隔几行空白如何填充)
  • 卷积神经网络实现彩色图像分类 - P2
  • 【博客694】k8s kubelet 状态更新机制
  • 【博客692】grafana如何解决step动态变化时可能出现range duration小于step
  • eNSP:ibgp的破水平切割练习
  • maven是什么?安装+配置
  • 基于长短期神经网络LSTM的多分类代码
  • 利用爬虫爬取图片并保存
  • 设计模式之Bridge模式的C++实现
  • springboot异步任务