深入探索位图技术:原理及应用

文章目录

  • 一、引言
  • 二、位图(Bitset)基础知识
    • 1、位图的概念
    • 2、位图的表示
    • 3、位图操作
  • 三、位图的应用场景
    • 1、数据查找与存储
    • 2、数据去重与排序
  • 四、位图的实现

一、引言

位图,以其高效、简洁的特性在数据处理、存储和检索等多个领域发挥着举足轻重的作用。通过二进制位的操作,位图能够实现对大量数据的快速访问、修改和查询,从而在众多实际应用场景中展现出其独特的优势。

随着大数据时代的来临,数据量呈现爆炸式增长,如何高效地处理这些数据成为了一个亟待解决的问题。位图技术以其对空间的高效利用和快速的位操作能力,成为了解决这一问题的有力工具。无论是在数据库系统、缓存机制、网络安全,还是在图形处理、用户权限管理等领域,位图都展现出了其不可或缺的价值。


二、位图(Bitset)基础知识

1、位图的概念

  • 位图及其基本组成单元(位)

位图(Bitmap)是一种基于二进制位的数据结构,用于高效地存储、检索和管理数据。其基本组成单元是位(Bit),即二进制数中的一个数字,其值只能是0或1。位图通常用于表示一组数据或某种状态的存在与否,其中每个数据项或状态都对应于位图中的一个或多个位。

在C++中,std::bitset是标准库提供的一种数据结构,用于表示固定大小的位序列,即一个固定长度的二进制序列。它提供了一组方法来进行位操作,例如设置、清除、翻转和测试位等。

std::bitset的大小在编译时确定,因此它是一种静态大小的位集合。你可以使用std::bitset来表示和处理布尔值序列,每个位可以代表一个布尔值(true或false)。而且可以单独访问每个位位置:例如,对于名为foo的位图,表达式foo[3]访问其第四个位,就像常规数组访问其元素一样。

在这里插入图片描述

  • 区分位图与像素图的概念

虽然位图在图形处理中也常被提及,但在此上下文中,我们需要明确区分两种不同类型的“位图”:一种是数据结构中的位图,如上所述,它主要用于数据的高效存储和检索;另一种是图形学中的位图,也被称为像素图,它是由像素(Pixel)组成的图像,每个像素都有其特定的颜色和位置。这两种位图在原理和应用上有本质的区别。数据结构中的位图关注的是数据的二进制表示和存储效率,而图形学中的位图则关注的是图像的视觉呈现和细节表现。

2、位图的表示

  • 使用二进制表示位图

位图,从数据结构的角度来看,是一种利用二进制位来标记数据存在性的高效方式。在二进制位图中,每一个二进制位(0或1)代表一个数据元素的状态:存在或不存在。通常,我们使用一个整数数组来实现位图,数组中的每个元素(如int或long类型)都由多个二进制位组成。

在这里插入图片描述

例如,如果我们使用一个32位的整数(int)来表示位图,那么每个整数可以表示32个不同的数据元素。当我们要标记第n个数据元素是否存在时,我们只需要找到对应的整数(通过n除以32得到整数索引),然后在该整数中找到对应的二进制位(通过n对32取余得到位索引),并将其设置为0或1。

  • 位图中位的编址和访问方式

在位图中,位的编址是基于其所在的整数和整数内的位位置来确定的。具体来说,如果我们有一个整数数组bitmap[],那么第n个数据元素对应的位在bitmap[n/32]的第(n%32)位上。

访问位图中的位通常涉及两个步骤:首先找到对应的整数,然后找到该整数中的对应位。这可以通过位运算来实现。例如,要设置第n位为1,我们可以使用以下代码:

int index = n / 32;      			// 计算整数索引
int position = n % 32;   			// 计算位索引
bitmap[index] |= (1 << position); 	// 设置对应位为1

同样地,要读取第n位的值,我们可以使用以下代码:

int index = n / 32;      							// 计算整数索引
int position = n % 32;   							// 计算位索引
int bitValue = (bitmap[index] >> position) & 1;  	// 读取对应位的值

这里的|=&=是位运算中的赋值操作符,分别表示按位或后赋值和按位与后赋值。<<>>是位移操作符,分别表示左移和右移。通过这些位运算操作,我们可以高效地访问和修改位图中的任意一位。

3、位图操作

在使用std::bitset时,常见的位操作包括设置位(setting a bit)、清除位(clearing a bit)、检测位(testing a bit)、翻转位(flipping a bit)等。

  1. 设置位(Setting a Bit)

要将std::bitset中的特定位设置为1,可以使用下标操作符[]配合赋值操作。

std::bitset<8> b; // 创建一个8位的bitset,所有位初始化为0
b[3] = 1;         // 设置第4位为1(bitset从右向左计数,从0开始)
  1. 清除位(Clearing a Bit)

要将std::bitset中的特定位清除(设置为0),同样可以使用下标操作符[]配合赋值操作。

std::bitset<8> b(0b11111111); // 创建一个8位的bitset,所有位初始化为1
b[3] = 0;                     // 清除第4位(设置为0)
  1. 检测位(Testing a Bit)

要检测std::bitset中的特定位是否为1,可以使用下标操作符[],这将返回一个可以转换为bool的类型。

std::bitset<8> b(0b10101010); 	// 创建一个8位的bitset
if (b[3])                  		// 检测第4位是否为1std::cout << "Bit 3 is set." << std::endl;
elsestd::cout << "Bit 3 is not set." << std::endl;
cout << b << endl;
// Bit 3 is set.
//10101010
  1. 翻转位(Flipping a Bit)

要翻转std::bitset中的特定位(从0变为1,或从1变为0),可以使用成员函数flip()

std::bitset<8> b(0b10101010); 	// 创建一个8位的bitset
b.flip(3);                   	// 翻转第4位
  1. 其他操作

std::bitset还提供了其他有用的成员函数,如:

  • size():返回bitset的大小(位数)。
  • count():返回bitset中设置为1的位数。
  • any():如果bitset中至少有一个位设置为1,则返回true。
  • none():如果bitset中所有位都设置为0,则返回true。
  • all():如果bitset中所有位都设置为1,则返回true。
  • to_ulong()to_ullong():将bitset转换为无符号长整型或无符号长长整型(如果bitset的大小允许)。
  • to_string():将bitset转换为字符串表示形式。
std::bitset<8> b(0b10101010);
std::cout << "Size: " << b.size() << std::endl;       	// 输出bitset的大小
std::cout << "Count: " << b.count() << std::endl;      	// 输出设置为1的位数
std::cout << "Any: " << b.any() << std::endl;          	// 检查是否有位设置为1
std::cout << "None: " << b.none() << std::endl;        	// 检查是否所有位都设置为0
std::cout << "All: " << b.all() << std::endl;          	// 检查是否所有位都设置为1
std::cout << "Value: " << b.to_ulong() << std::endl;   	// 转换为无符号长整型并输出
std::cout << "String: " << b.to_string() << std::endl; 	// 转换为字符串并输出

在这里插入图片描述


三、位图的应用场景

1、数据查找与存储

  • 使用位图实现快速数据查找

位图可以用于快速查找某个元素是否存在。例如,如果有一个包含大量整数的集合,并且整数的范围已知(例如,从1到1亿),那么可以使用一个位图来表示这个集合。每个整数对应位图中的一个位,如果该整数在集合中,则对应的位被设置为1,否则为0。这样,查找某个整数是否存在只需要检查其对应的位即可,时间复杂度为O(1)。

  • 位图在数据存储中的优势

空间效率:相比于存储原始数据,位图可以显著节省存储空间。在上面的例子中,如果使用一个整型数组来存储集合中的元素,每个整数需要4个字节(假设是32位系统),那么存储1亿个整数需要大约400MB的空间。而使用位图,只需要大约12MB的空间(1亿个位,每个位1/8字节)。

  • 使用整型数组:如果每个整数占用4个字节(在32位系统中,一个int通常是32位,即4字节),那么存储1亿个整数将需要大约400MB的空间,计算如下:

    1亿个整数 * 4字节/整数 = 400,000,000字节  
    400,000,000字节 / 1024 / 1024 = 381.47MB (约等于400MB)
    
  • 使用位图:在位图中,每个位占用1/8字节(因为1字节 = 8位)。所以,存储1亿个位将需要大约12MB的空间,计算如下:

    1亿个位 * 1/8字节/位 = 12,500,000字节  
    12,500,000字节 / 1024 / 1024 = 11.92MB (约等于12MB)
    

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

步骤 1: 确定位图大小

首先,需要确定无符号整数的位数,这决定了位图的大小。假设我们处理的是32位无符号整数,那么整数的范围是从0到232 - 1。因此,你需要一个位图,其中包含232个位,每个位对应一个可能的整数。

步骤 2: 分配内存

接下来,就需要分配足够的内存来存储这个位图。由于每个位可以是0或1,可以使用位操作来紧凑地存储这些位。在实际应用中,通常会使用一个字节数组(byte array)或位数组(bit array)来表示位图。

对于一个包含232个位的位图,你需要大约512MB的内存(因为232位 / 8位/字节 = 229字节 = 512MB)。

步骤 3: 初始化位图

将位图中的所有位初始化为0,表示没有任何整数被标记为存在。

步骤 4: 填充位图

遍历40亿个无符号整数,对于每个整数,计算它在位图中的索引,并将该索引对应的位设置为1。索引的计算通常是通过整数本身直接转换得到的。例如,对于一个32位整数num,你可以直接将其用作索引(可能需要一些转换来适应字节数组的索引方式)。

步骤 5: 查询整数

当需要查询一个整数是否存在于集合中时,你只需计算该整数在位图中的索引,并检查该索引对应的位是否为1。如果是1,表示该整数存在于集合中;如果是0,表示不存在。

有了上面的思路方法,我们来解决如下问题:

一、给定100亿个整数,我们如何找到只出现一次的整数呢?

由于整数可能有正有负,我们先假设整数的范围是已知的,例如是32位有符号整数。使用一个标准的位图来记录每个整数出现的次数。但需要扩展位图的概念,使得每个整数对应多个位,用以计数。例如,可以使用2个位来表示一个整数出现的次数:00表示0次,01表示1次,10表示2次或更多。

📽 我们可以这样做:

初始化一个大小为2 * INT_MAX + 1的位图(考虑负数和0),每个整数对应2位。

遍历整数集合,对每个整数更新其对应的计数器。

  • 如果对应位是00,则设置为01。
  • 如果是01,则设置为10。
  • 如果是10,则保持不变(因为我们只关心出现1次的)。
    再次遍历位图,找出所有对应位为01的整数。

二、给两个文件,分别有100亿个整数,我们只有1G内存,如何找到?

首先,假设这些整数是32位无符号整数,那么理论上需要4GB的内存来存储一个完整的位图(因为232位 = 4GB)。由于只有1GB的内存可用,因此不能一次性加载所有整数到位图中。

因此我们借助哈希函数,分块处理。

  1. 准备阶段
    • 先设计一个哈希函数。这个函数的任务是,当我们给它一个整数时,它会告诉我们这个整数应该属于哪个“小团队”。想象一下,我们有1000个“小团队”,每个团队负责处理大约1000万个整数。
  2. 处理第一个文件
    • 我们开始遍历第一个文件,对里面的每个整数都用哈希函数“问问路”,看它们应该属于哪个“小团队”。
    • 比如,哈希函数告诉我们某个整数应该属于“团队500”,那我们就把这个整数记录到 “a500” 这个文件里。
    • 这样,我们就把第一个大文件拆分成了1000个小文件,每个文件大约40M,这样我们的1G内存就能轻松应对了。
  3. 处理第二个文件
    • 对第二个文件也如法炮制。还是使用相同的哈希函数,把整数分配到它们各自的“小团队”中。
    • 这次我们把结果记录在b1, b2, …, b1000这一系列文件中。
  4. 找交集
    • 有了这两组“小团队”,我们就可以开始找交集了。
    • 由于我们是用同样的哈希函数来分配整数的,所以,如果两个文件中有共同的整数,那么这些整数一定会出现在同样编号的“小团队”里。
    • 比如,a500和b500里就应该有相同的整数,我们只需要在这两个文件里找交集就行了。
    • 这样,我们就在每个“小团队”内部找交集,由于数据量小了很多,这个任务就变得容易多了。
  5. 汇总成果
    • 最后,我们把所有“小团队”找到的交集汇总起来,就是我们要找的答案了。

2、数据去重与排序

使用位图去除数据集中的重复元素。

基于位图的排序算法通常适用于数据值范围已知且较小的情况。其原理是利用位图来记录每个数据值的出现情况,并根据位图的顺序生成已排序的数组。具体步骤如下:

  1. 初始化位图:创建一个能够覆盖所有数据值的位图,并初始化为0。
  2. 遍历并设置位图:遍历原始数据,对于每个数据值,将其对应的位在位图中设置为1。
  3. 生成排序数组:从位图的最低位开始,依次检查每个位。如果某个位为1,则表示其对应的数据值存在,将其添加到排序数组中。继续这个过程,直到检查完位图的所有位。

四、位图的实现

template<size_t N>
class bitset {
public:bitset( ) {_bits.resize(N / 32 + 1, 0);}//	把 x 映射的位 标记成 1void set(size_t x) {assert(x < N);size_t i = x / 32;size_t j = x % 32;_bits[i] |= (1 << j);}//	把 x 映射的位 标记成 0void reset(size_t x) {assert(x < N);size_t i = x / 32;size_t j = x % 32;_bits[i] &= ~(1 << j);}bool test(size_t x) {size_t i = x / 32;size_t j = x % 32;return _bits[i] & (1 << j);}
private:vector<int> _bits;
};

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/293057.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

Nest安装及使用~

前提条件 请确保您的操作系统上安装了 Node.js&#xff08;版本 > 16&#xff09; &#x1f4da;要查看指南&#xff0c;请访问 https://docs.nestjs.com/ &#x1f4da;要查看中文 指南&#xff0c; 请访问 https://docs.nestjs.cn/ $ node -v v16.18.1 $ npm -v 7.x.x安…

【C++】C++11的新特性

目录 一. 列表初始化1. 列表初始化的原理: initializer_list 二. 类型的声明1. auto2. decltype 三. nullptr四. 范围 for五. STL容器变化六. 类的新功能 一. 列表初始化 在 C 语言中, 就可以使用 {} 对数组或结构体进行初始化, 而 C11 扩大了 {} 的使用范围, 使其可以初始化所…

Mysql-数据库范式和Mysql安装

文章目录 数据库三范式第一范式&#xff1a;1NF第二范式&#xff1a;2NF第三范式&#xff1a;3NF Yum安装CentOS7 yum安装解决“Access denied”拒绝访问异常 数据库三范式 第一范式&#xff1a;1NF 第一范式&#xff1a;数据库中无重复的列&#xff0c;每一列都是不可分割的…

乐乐音乐鸿蒙版-支持krc歌词(动感歌词、翻译和音译歌词)

简介 乐乐音乐主要是基于HarmonyOS开发的音乐播放器&#xff0c;它支持lrc歌词和动感歌词(ksc歌词、krc歌词和hrc歌词等)、多种格式歌词转换器及制作动感歌词、翻译歌词和音译歌词。 开发环境 ArkTS、Stage模型、SDK3.1、 API 9 注&#xff1a;没试过在真机条件下调试。 功…

Java基础学习: JDK动态代理

文章目录 一、什么是JDK动态代理二、JDK动态代理的特点三、JDK动态代理类如何使用四、JDK动态代理原理分析1、创建代理对象2、生成代理类 一、什么是JDK动态代理 JDK动态代理是Java提供的一种动态生成代理类和代理对象的技术。它主要利用Java的反射机制实现&#xff0c;在运行…

Open CASCADE学习|GeomFill_Frenet

GeomFill_Frenet继承自GeomFill_TrihedronLaw类。GeomFill_Frenet类主要用于实现Frenet标架的计算。Frenet标架是一个沿曲线移动的局部坐标系&#xff0c;它由切向量、法向量和副法向量组成&#xff0c;常用于机器人学、计算机图形学等领域。 class GeomFill_Frenet : publi…

docker 数据卷

Docker数据卷是Docker中的一个核心机制&#xff0c;用于实现容器间数据的持久化和共享。它是宿主机上的一个特殊目录&#xff0c;可以供一个或多个容器使用。容器删除时&#xff0c;不会删除其挂载的数据卷&#xff0c;也不会存在类似的垃圾机制对容器存在的数据卷进行处理。 …

每日面经分享(Spring Boot: part2 DAO层)

1. Spring Boot DAO层的作用 a. 封装数据访问逻辑&#xff1a;DAO层的主要责任是封装与数据访问相关的逻辑。负责处理与数据库的交互&#xff0c;包括数据的增删改查等操作。通过将数据访问逻辑统一封装在DAO层中&#xff0c;可以提高代码的可维护性和可重用性。 b. 解耦业务逻…

【vue3学习笔记(二)】(第141-143节)初识setup;ref函数_处理基本类型;ref函数_处理对象类型

尚硅谷Vue2.0Vue3.0全套教程丨vuejs从入门到精通 本篇内容对应课程第141-143节 课程 P141节 《初识setup》笔记 1、setup是所有组合式API“表演的舞台”&#xff0c;组件中所用到的所有数据、方法、监视数据、生命周期钩子等都需要配置在setup中。 2、setup的两种返回值&…

【Linux】socket套接字

欢迎来到Cefler的博客&#x1f601; &#x1f54c;博客主页&#xff1a;折纸花满衣 &#x1f3e0;个人专栏&#xff1a;题目解析 目录 &#x1f449;&#x1f3fb;IP地址和端口号pid和port的关系 &#x1f449;&#x1f3fb;TCP和UDP&#x1f449;&#x1f3fb;网络字节序&…

NineData与StarRocks商业化运营公司镜舟科技完成产品兼容认证

近日&#xff0c;镜舟科技与NineData完成产品兼容测试。在经过联合测试后&#xff0c;镜舟科技旗下产品与NineData云原生智能数据管理平台完全兼容&#xff0c;整体运行高效稳定。 镜舟科技致力于帮助中国企业构建卓越的数据分析系统&#xff0c;打造独具竞争力的“数据护城河”…

2-HDFS常用命令及上传下载流程

HDFS NameNode 安全模式(safemode) 当NameNode被重启的时候&#xff0c;自动进入安全模式 在安全模式中&#xff0c;NameNode首先会触发edits_inprogress文件的滚动。滚动完成之后&#xff0c;更新fsimage文件 更新完成之后&#xff0c;NameNode会将fsimage文件中的元数据加…

STM32——超声测距HC_SR04记录

一、HC_SR04简述 HC-SR04超声波测距模块可提供 2cm-400cm的非接触式距离感测功能&#xff0c;测距精度可达高到 3mm&#xff1b;模块包括超声波发射器、接收器与控制电路。 基本工作原理&#xff1a; (1)采用IO 口TRIG 触发测距&#xff0c;给最少10us 的高电平信呈。 (2)模块…

一文教你轻松领取华为云优惠券

随着云计算技术的快速发展&#xff0c;越来越多的企业和个人选择使用云服务来满足他们的需求。华为云作为全球领先的云服务提供商之一&#xff0c;为用户提供了丰富的产品和服务。为了帮助用户更好地体验华为云服务&#xff0c;本文将为大家详细介绍如何轻松领取华为云优惠券。…

Taskflow:限制最大并发度( Limit the Maximum Concurrency)

定义信号量Semaphore Taskflow提供了一个机制&#xff0c;tf::Semaphore&#xff0c;用于限制任务部分中的最大并发。您可以让任务在执行工作之前/之后获取/释放一个或多个信号量。一项任务可以获取和释放信号量&#xff0c;或者只是获取或只是释放它。tf::Semaphore对象以初始…

MySQL介绍

1 什么是Mysql MySQL是一个开源的关系型数据库管理系统&#xff08;RDBMS&#xff09;&#xff0c;它使用结构化查询语言&#xff08;SQL&#xff09;进行数据库管理。自上世纪90年代中期以来&#xff0c;MySQL凭借其易用性、稳定性和高效性能&#xff0c;赢得了广泛的用户群体…

政安晨:【Keras机器学习实践要点】(三)—— 编写组件与训练数据

目录 介绍 编写组件 训练模型 政安晨的个人主页&#xff1a;政安晨 欢迎 &#x1f44d;点赞✍评论⭐收藏 收录专栏: TensorFlow与Keras机器学习实战 希望政安晨的博客能够对您有所裨益&#xff0c;如有不足之处&#xff0c;欢迎在评论区提出指正&#xff01; 介绍 通过 Ker…

手写简易操作系统(十七)--编写键盘驱动

前情提要 上一节我们实现了锁与信号量&#xff0c;这一节我们就可以实现键盘驱动了&#xff0c;访问键盘输入的数据也属于临界区资源&#xff0c;所以需要锁的存在。 一、键盘简介 之前的 ps/2 键盘使用的是中断驱动的&#xff0c;在当时&#xff0c;按下键盘就会触发中断&a…

Abaqus周期性边界代表体单元Random Sphere RVE 3D (Mesh)插件

插件介绍 Random Sphere RVE 3D (Mesh) - AbyssFish 插件可在Abaqus生成三维具备周期性边界条件(Periodic Boundary Conditions, PBC)的随机球体骨料及骨料-水泥界面过渡区(Interfacial Transition Zone, ITZ)模型。即采用周期性代表性体积单元法(Periodic Representative Vol…

1.8 python 模块 time、random、string、hashlib、os、re、json

ython之模块 一、模块的介绍 &#xff08;1&#xff09;python模块&#xff0c;是一个python文件&#xff0c;以一个.py文件&#xff0c;包含了python对象定义和pyhton语句 &#xff08;2&#xff09;python对象定义和python语句 &#xff08;3&#xff09;模块让你能够有逻辑地…