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

文章目录

  • 一、引言
  • 二、位图（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位是否为1
    std::cout << "Bit 3 is set." << std::endl;
else
    std::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 映射的位 标记成 1
    void set(size_t x) {
        assert(x < N);
        size_t i = x / 32;
        size_t j = x % 32;

        _bits[i] |= (1 << j);
    }
    //	把 x 映射的位 标记成 0
    void 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;
};

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

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

抽象类和接口的简单认识

抽象类和接口的简单认识

目录 一、抽象类 1.什么是抽象类 2.抽象类的注意事项 3.抽象类与普通类的对比 二、接口 1.接口的简单使用 2.接口的特性 3.接口的使用案例 4.接口和抽象类的异同 一、抽象类 所谓抽象类&#xff0c;就是更加抽象的类&#xff0c;也就是说&#xff0c;这个类不能具体描…
阅读更多...
文献学习-23-MRM：用于遗传学医学图像预训练的掩码关系建模

文献学习-23-MRM：用于遗传学医学图像预训练的掩码关系建模

MRM: Masked Relation Modeling for Medical Image Pre-Training with Genetics Authors: Qiushi Yang, Wuyang Li, Baopu Li, Yixuan Yuan Source: ICCV 2023 Abstract: 关于自动多模态医疗诊断的 ODERN 深度学习技术依赖于大量的专家注释&#xff0c;这既耗时又令人望而却…
阅读更多...
【KingSCADA】播放语音

【KingSCADA】播放语音

1.函数介绍 PlaySound(string strWaveFileName, int nMode);下面是官方帮助文档中的解释&#xff1a; 2.生成语音文件 3.使用脚本播放音频文件 将音频文件存放在工程目录下面&#xff0c;我存放在了…\Resources\文件夹下&#xff1a; 我简单的写了一个定时1分钟播放一次语…
阅读更多...
【MATLAB源码-第23期】基于matlab的短时傅里叶STFT信号变换仿真，得到信号的时频曲线图。

【MATLAB源码-第23期】基于matlab的短时傅里叶STFT信号变换仿真，得到信号的时频曲线图。

操作环境&#xff1a; MATLAB 2022a 1、算法描述 短时傅里叶变换&#xff08;Short-Time Fourier Transform&#xff0c;STFT&#xff09;是傅里叶变换的一种扩展&#xff0c;用于分析信号在时域和频域上的变化。描述如下&#xff1a; 1. **时域与频域分析**&#xff1a; …
阅读更多...
使用 Seq2Seq 模型进行文本摘要

使用 Seq2Seq 模型进行文本摘要

目录 引言 1 导入数据集 2 清洗数据集 3 确定允许的最大序列长度 4 选择合理的文本和摘要 5 对文本进行标记 6 删除空文本和摘要 7 构建模型 7.1 编码器 7.2 解码器 8 训练模型 9 测试模型 10 注意 11 整体代码 引言 文本摘要是指在捕捉其本质的同时缩短长文本的…
阅读更多...
windows平台虚拟机安装

windows平台虚拟机安装

windows平台虚拟机安装 1. 安装VMwareWorkstationPro 1.1 软件下载 官网下载 官网 百度网盘下载 版本 VMwareWorkstationPro16 链接&#xff1a;https://pan.baidu.com/s/1LidMxoM9e4a4CANixyRoyg?pwd1157 提取码&#xff1a;1157 1.2 软件安装 软件安装注意事项 软件…
阅读更多...
Mamba和状态空间模型(SSM)的视觉指南：替代 Transformers 的语言建模方法

Mamba和状态空间模型(SSM)的视觉指南：替代 Transformers 的语言建模方法

原文地址&#xff1a; A Visual Guide to Mamba and State Space Models 2024 年 2 月 19 日 论文地址&#xff1a;https://arxiv.org/pdf/2312.00752.pdf 这篇论文介绍了一种新型的线性时间序列模型Mamba&#xff0c;它通过选择性状态空间&#xff08;Selective State Space…
阅读更多...
详解CAS（Compare and swap）

详解CAS（Compare and swap）

一、什么是 CAS CAS: 全称Compare and swap&#xff0c;字⾯意思:”⽐较并交换“&#xff0c;⼀个 CAS 涉及到以下操作&#xff1a; 我们假设内存中的原数据V&#xff0c;旧的预期值A&#xff0c;需要修改的新值B。 比较 A 与 V 是否相等。&#xff08;⽐较&#xff09; 如果…
阅读更多...
【A-013】基于SSH的共享单车管理系统/共享单车出租系统

【A-013】基于SSH的共享单车管理系统/共享单车出租系统

【A-013】基于SSH的共享单车管理系统/共享单车出租系统 开发环境&#xff1a; Eclipse/MyEclipse、Tomcat8、Jdk1.8 数据库&#xff1a; MySQL 适用于&#xff1a; 课程设计&#xff0c;毕业设计&#xff0c;学习等等 系统介绍&#xff1a; 基于SSH开发的共享单车管理系统/…
阅读更多...
python mysql错误如何处理

python mysql错误如何处理

错误代码类型&#xff1a;pymysql.err.InternalError: (1054, "Unknown column jack in field list") import pymysql d_mysql {host: 127.0.0.1, port: 33333,user: *****,password: *****,db: *****,charset: utf8} conn pymysql.connect(**d_mysql) cur co…
阅读更多...
Latex自学以及安装使用教程

Latex自学以及安装使用教程

你就按部就班的来&#xff0c;准没问题。 Step1&#xff1a;下载Tex live和Tex studio&#xff0c;安装教程参考自&#xff1a;LaTeX的安装教程&#xff08;Texlive 2020 TeX studio&#xff09; Step2: (非必要&#xff09;vscodeLatex&#xff0c;参考自:使用VSCode编写LaTe…
阅读更多...
基于OrangePi Zero2的智能家居项目（开发阶段）

基于OrangePi Zero2的智能家居项目（开发阶段）

智能家居项目的软件实现 紧接上文 基于OrangePi Zero2的智能家居项目&#xff08;准备阶段&#xff09;-CSDN博客 目录 一、项目整体设计 1.1项目整体设计 1.2具体划分 二、开发工作的前期准备 1、进行分类&#xff0c;并用Makefile文件进行管理 参考&#xff1a;自己创…
阅读更多...
条形图、柱状图的绘制方法

条形图、柱状图的绘制方法

【题目描述】 用*号输出柱状图。第一行输入一个整数n表示数据个数&#xff0c;第二行输入n个整数&#xff0c;用空格隔开。n和输入的数都不超过20。 【样例输入】 7 5 1 1 8 1 1 5 【样例输出】 1&#xff0e;条形图&#xff08;水平柱状图&#xff09; 样例中的柱状图属…
阅读更多...
C++刷题篇——06整理扑克牌

C++刷题篇——06整理扑克牌

一、题目 二、解题思路 特别注意多组三张两张组合的情况 具体思路的见代码注释部分 三、代码 #include<iostream> #include<vector> #include<string> #include<map> #include<algorithm>using namespace std;vector<int>split(string p…
阅读更多...
2-Prometheus监控主机

2-Prometheus监控主机

文章目录 1 介绍2 部署2.1 下载2.2 解压到指定目录2.3 配置进程管理2.4 程序启动参数2.5 启动和监听 3 添加到 Prometheus4. 指标4.1 通过页面查看指标数据4.2 查看都有哪些指标4.3 指标数据规范 5 程序运行参数 1 介绍 Prometheus 使用 node_exporter 服务程序监控 Linux 主机…
阅读更多...
【前端面试3+1】07vue2和vue3的区别、vue3响应原理及为什么使用proxy、vue的生命周期中在什么时期给接口发请求、【找出数组最大公约数】

【前端面试3+1】07vue2和vue3的区别、vue3响应原理及为什么使用proxy、vue的生命周期中在什么时期给接口发请求、【找出数组最大公约数】

一、vue2和vue3的区别 1.性能优化&#xff1a; Vue 3在性能方面有很大的提升&#xff0c;主要是通过虚拟DOM的优化和响应式系统的改进实现的。 虚拟 DOM 重构&#xff1a;Vue 3 中对虚拟 DOM 进行了重构&#xff0c;使得更新算法更加高效&#xff0c;减少了更新时的开销&#x…
阅读更多...
LCX端口转发

LCX端口转发

LCX介绍 LCX是一款端口转发工具&#xff0c;分为Windows版和Linux版&#xff0c;Linux版本为PortMap。LCX有端口映射和端口转发两大功能&#xff0c;例如当目标的3389端口只对内开放而不对外开放时&#xff0c;可以使用端口映射将3389端口映射到目标的其他端口使用&#xff1b…
阅读更多...
iOS问题记录 - App Store审核新政策：隐私清单 SDK签名（持续更新）

iOS问题记录 - App Store审核新政策：隐私清单 SDK签名（持续更新）

文章目录 前言开发环境问题描述问题分析1. 隐私清单 & SDK签名1.1. 隐私清单 - 数据使用声明1.2. 隐私清单 - 所用API原因描述1.3. SDK签名 2. 即将发布的第三方SDK要求 解决方案最后 前言 前段时间用Flutter开发的iOS App提交了新版本&#xff0c;结果刚过两分钟就收到了…
阅读更多...
属性选择器

属性选择器

1.[title]{background:yellow;}&#xff1a;所有带title标签设置成黄色 2.div[class]{background:yellow;}&#xff1a;所有div中带class标签设置成黄色 3.div[classbox1]{border:1px solid blue; }&#xff1a;div中包含class并且classbox1的设置成蓝边框 4. class…
阅读更多...
【春秋云镜】CVE-2023-7106标靶Wp

【春秋云镜】CVE-2023-7106标靶Wp

0x01&#xff1a;漏洞点 老样子先&#xff0c;看看标题介绍奥 ok了解到了 我们现在要知道参数是prod_id&#xff0c;路径为/pages/product_details.php 0x02&#xff1a;操作 直接打开SQLmap一把梭 sqlmap -u {URL}/pages/product_details.php?prod_id1 --current-db 这里…
阅读更多...
最新文章

Copyright @ 2022~2023