数据结构——bitset(位图)模拟实现

2024-06-11 18:44

本文主要是介绍数据结构——bitset(位图)模拟实现,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

从一个题目引出位图

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

这里有两种大家容易想到的解法:

1.遍历搜索,时间复杂度为O(N)

2.先排序(O(NlogN)) ,然后利用二分查找搜索(O(logN))

上面两种方法虽然简单,但是一方面是需要的时间太久,一个内存可能没有这么大的空间用来开辟40亿个无符号整数。若是我们要将这些数全部加载到内存当中,那么将会占用16G的空间。

3.位图解决

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

无符号整数总共有2^32个,因此记录这些数字就需要2^32个比特位,也就是512M的内存空间,内存消耗大大减少。

这里就引出位图的概念:

位图的概念

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

位图的构造函数

构造函数一般可以直接复用reset函数进行实现:

第一种: N/32 + 1

首先要知道,一个整形int有32位,所以我们用数据个数直接除32即可。但是,假如N为33,多出来的1位就会没位置放了,所以一般这里会多预留一个32位,也就是+1

第二种:(N>>5) + 1

 这里使用到了移位运算符>>和<<,这里的N>>5,实际上就是让数据个数从高位向低位移动,总共移动5次,也就是除以2^5,也就是除以32,这里结果是和第一种方法相同,只是方法不同。

 

        bitset()//构造函数{_bits.resize(N / 32 + 1);//利用resize函数构造初始化为0//_bits.resize((N>>5)+1);}

位图的定义

第一种:构造一个8位的位图,所有为初始化为0

bitset<8> bs1; //00000000

第二种:构造一个8位的位图,根据所给的值初始化位图前N位 

bitset<8> bs2(100); //01100100

第三种:构造一个8位的位图,根据字符串中的0/1序列来初始化位图的前N位

bitset<8> bs2(string("111001")); //00111001

位图的set函数 

set函数的使用

	bitset<8> bs;bs.set(2); //设置第2位bs.set(4); //设置第4位cout << bs << endl; //00010100

set函数的模拟实现

方法如下:

  1. 计算出该位位于第 i 个整数的第 j 个比特位。
  2. 将1左移 j 位后与第 i 个整数进行或运算即可。(因为别的位不能受到影响)

        //设置位void set(size_t x){size_t i = x / 32;//先获取在第i个整数size_t j = x % 32;//再获取在第j个位_bits[i] |= (1 << j);//将该位设置成1}

位图的reset函数

reset函数的使用

	bitset<8> bs;bs.set(2); //设置第2位bs.set(4); //设置第4位cout << bs << endl; //00010100bs.reset(2); //清空第0位cout << bs << endl; //00010000bs.reset(4); //清空第0位cout << bs << endl; //00000000

reset的模拟实现

方法如下:

  1. 计算出该位位于第 i 个整数的第 j 个比特位。
  2. 将1左移 j 位后与第 i 个整数进行异或运算即可。
        void reset(size_t x){size_t = i = x / 32;//先获取在第几个整数size_t = j = x % 32;//再获取在第几个位_bits[i] &= (~(1 << j));//然后将该位设置成0}

这篇关于数据结构——bitset(位图)模拟实现的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1051984

相关文章

Python实现终端清屏的几种方式详解

《Python实现终端清屏的几种方式详解》在使用Python进行终端交互式编程时,我们经常需要清空当前终端屏幕的内容,本文为大家整理了几种常见的实现方法,有需要的小伙伴可以参考下... 目录方法一:使用 `os` 模块调用系统命令方法二:使用 `subprocess` 模块执行命令方法三:打印多个换行符模拟

SpringBoot+EasyPOI轻松实现Excel和Word导出PDF

《SpringBoot+EasyPOI轻松实现Excel和Word导出PDF》在企业级开发中,将Excel和Word文档导出为PDF是常见需求,本文将结合​​EasyPOI和​​Aspose系列工具实... 目录一、环境准备与依赖配置1.1 方案选型1.2 依赖配置(商业库方案)二、Excel 导出 PDF

Python实现MQTT通信的示例代码

《Python实现MQTT通信的示例代码》本文主要介绍了Python实现MQTT通信的示例代码,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一... 目录1. 安装paho-mqtt库‌2. 搭建MQTT代理服务器(Broker)‌‌3. pytho

使用zip4j实现Java中的ZIP文件加密压缩的操作方法

《使用zip4j实现Java中的ZIP文件加密压缩的操作方法》本文介绍如何通过Maven集成zip4j1.3.2库创建带密码保护的ZIP文件,涵盖依赖配置、代码示例及加密原理,确保数据安全性,感兴趣的... 目录1. zip4j库介绍和版本1.1 zip4j库概述1.2 zip4j的版本演变1.3 zip4

python生成随机唯一id的几种实现方法

《python生成随机唯一id的几种实现方法》在Python中生成随机唯一ID有多种方法,根据不同的需求场景可以选择最适合的方案,文中通过示例代码介绍的非常详细,需要的朋友们下面随着小编来一起学习学习... 目录方法 1:使用 UUID 模块(推荐)方法 2:使用 Secrets 模块(安全敏感场景)方法

Spring StateMachine实现状态机使用示例详解

《SpringStateMachine实现状态机使用示例详解》本文介绍SpringStateMachine实现状态机的步骤,包括依赖导入、枚举定义、状态转移规则配置、上下文管理及服务调用示例,重点解... 目录什么是状态机使用示例什么是状态机状态机是计算机科学中的​​核心建模工具​​,用于描述对象在其生命

Spring Boot 结合 WxJava 实现文章上传微信公众号草稿箱与群发

《SpringBoot结合WxJava实现文章上传微信公众号草稿箱与群发》本文将详细介绍如何使用SpringBoot框架结合WxJava开发工具包,实现文章上传到微信公众号草稿箱以及群发功能,... 目录一、项目环境准备1.1 开发环境1.2 微信公众号准备二、Spring Boot 项目搭建2.1 创建

IntelliJ IDEA2025创建SpringBoot项目的实现步骤

《IntelliJIDEA2025创建SpringBoot项目的实现步骤》本文主要介绍了IntelliJIDEA2025创建SpringBoot项目的实现步骤,文中通过示例代码介绍的非常详细,对大家... 目录一、创建 Spring Boot 项目1. 新建项目2. 基础配置3. 选择依赖4. 生成项目5.

Linux下删除乱码文件和目录的实现方式

《Linux下删除乱码文件和目录的实现方式》:本文主要介绍Linux下删除乱码文件和目录的实现方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录linux下删除乱码文件和目录方法1方法2总结Linux下删除乱码文件和目录方法1使用ls -i命令找到文件或目录

SpringBoot+EasyExcel实现自定义复杂样式导入导出

《SpringBoot+EasyExcel实现自定义复杂样式导入导出》这篇文章主要为大家详细介绍了SpringBoot如何结果EasyExcel实现自定义复杂样式导入导出功能,文中的示例代码讲解详细,... 目录安装处理自定义导出复杂场景1、列不固定,动态列2、动态下拉3、自定义锁定行/列,添加密码4、合并