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

C++笔记---位图

1. 位图的概念

位图(Bitmap)是一种基于位操作的数据结构,用于表示一组元素的集合信息。它通常是一个仅包含0和1的数组,每个元素对应一个二进制位,若该元素存在,则对应的位为1;若不存在,则为0。位图的这种表示方式使得它能够在存储上以极高的空间效率来管理大规模数据。位图特别适用于需要频繁查询和更新的场景,如数据库索引、图像处理和网络协议等。

简单来说,就是一个采用直接定址法的哈希表,只不过一个bit位映射一个数。

底层通常是一个存储整形的数组或vector,将其中的整形数据连起来看作一个存储bit位的数组。下标为n的bit位为1代表n存在,为0代表n不存在。

这样一来,位图存储一个数据的消耗仅为一个bit位,相比于红黑树和哈希表,在对大量的整形数据的进行增删查改时,位图的优势就十分明显了。

优点:增删查改效率极高,空间复杂度低。

缺点:只适用于整型。

2. 位图的实现

STL的 "bitset" 就是位图,其有三个主要接口:set(插入),reset(删除),test(查找)。

bitset - C++ Reference

位图的实现比较简单,就不过多介绍了。

namespace lbz
{template<size_t N>class bitset{public:bitset():_bs(N / 32 + 1, 0){}void set(size_t x){size_t i = x / 32;size_t j = x % 32;_bs[i] |= (1 << j);}void reset(size_t x){size_t i = x / 32;size_t j = x % 32;_bs[i] &= ~(1 << j);}bool test(size_t x){size_t i = x / 32;size_t j = x % 32;return _bs[i] & (1 << j);}private:vector<int> _bs;};

 注意,这里无需在意大小端的问题,因为bit 位的下标只是假想的下标。

我们只需要算出代表x的bit位是哪一个整形中的第几个,并保证各个接口采用相同的逻辑查找即可。

3. 位图的应用

3.1 检查数据是否存在

eg:给40亿个不重复的无符号整数,没排过序。如何判断某个无符号数是否在这40亿个数中?(腾讯、百度等公司出过的面试题)。

思路1:暴力遍历--->时间复杂度O(N),太慢

思路2:排序+二分查找--->时间复杂度O(N * logN) + O(logN),排序消耗大,但是排好序之后可以进行多次查找。

但是上面两种思路都存在着一个问题,那就是需要将40亿个整数存到内存中。

40亿个整数约等于16GB,考虑到电脑中的其他进程,开出这么大的一个数组显然是不现实的。

这时候就可以使用位图来解决,位图中开辟 "UINT_MAX" 个字节(数据范围为0~UINT_MAX),并将数据存储到位图中。此时,数据对内存的占用就可以降低到500MB左右,且查找效率为O(1)

3.2 计算数据个数

eg:给100亿个不重复的无符号整数,没排过序。如何找出出现次数小于2的数据?

一个bit位只能判断存不存在,如果要计数,就只能用多个比特位来映射一个数。

这里,我们可以采用包装多个位图的方式来实现,第一个位图存储第一个bit位,第二个位图存储第二个bit位,以此类推。

template<size_t N>
class two_bitset
{
public:void set(size_t x){bool bit1 = _bs1.test(x);bool bit2 = _bs2.test(x);if (!bit1 && !bit2)// 00 + 1{_bs2.set(x);}else if (!bit1 && bit2)// 01 + 1{_bs1.set(x);_bs2.reset(x);}else if (bit1 && !bit2)// 10 + 1{_bs2.set(x);}}void reset(size_t x){_bs1.reset(x);_bs2.reset(x);}int test(size_t x){bool bit1 = _bs1.test(x);bool bit2 = _bs2.test(x);if (!bit1 && !bit2)// 00{return 0;}else if (!bit1 && bit2)// 01{return 1;}else if (bit1 && !bit2)// 10{return 2;}else{return 3;}}
private:bitset<N> _bs1;bitset<N> _bs2;
};

先简单介绍一下,之后可能更新。

相关文章:

C++笔记---位图

1. 位图的概念 位图&#xff08;Bitmap&#xff09;是一种基于位操作的数据结构&#xff0c;用于表示一组元素的集合信息。它通常是一个仅包含0和1的数组&#xff0c;每个元素对应一个二进制位&#xff0c;若该元素存在&#xff0c;则对应的位为1&#xff1b;若不存在&#xff…...

ABC370

## A - Raise Both Hands &#xff08;模拟&#xff09; 题意&#xff1a;输入l&#xff0c;r&#xff0c;如果l1r0输出yes&#xff0c;l0r1输出no&#xff0c;否则输出Invalid 代码&#xff1a; #include<bits/stdc.h> using namespace std; typedef long long ll; vo…...

C语言[求x的y次方]

C语言——求x的y次方 这段 C 代码的目的是从用户输入获取两个整数 x 和 y &#xff0c;然后计算 x 的 y 次幂&#xff08;不过这里有个小错误&#xff0c;实际计算的是 x 的 (y - 1) 次幂&#xff0c;后面会详细说&#xff09;&#xff0c;最后输出结果。 代码如下: #include…...

JavaScript part2

一.前言 前面我们讲了一下js的基础语法&#xff0c;但是这些还是远远不够的&#xff0c;我们要想操作标签&#xff0c;实现一个动态且好看的页面&#xff0c;就得学会BOM和DOM&#xff0c;这些都是浏览器和页面的&#xff0c;这样我们才能实现一个好看的页面 二.BOM对象 BOM…...

HarmonyOS开发 - 本地持久化之实现LocalStorage实例

用户首选项为应用提供Key-Value键值型的数据处理能力&#xff0c;支持应用持久化轻量级数据&#xff0c;并对其修改和查询。数据存储形式为键值对&#xff0c;键的类型为字符串型&#xff0c;值的存储数据类型包括数字型、字符型、布尔型以及这3种类型的数组类型。 说明&#x…...

【C++打怪之路Lv12】-- 模板进阶

#1024程序员节&#xff5c;征文# &#x1f308; 个人主页&#xff1a;白子寰 &#x1f525; 分类专栏&#xff1a;重生之我在学Linux&#xff0c;C打怪之路&#xff0c;python从入门到精通&#xff0c;数据结构&#xff0c;C语言&#xff0c;C语言题集&#x1f448; 希望得到您…...

第23周Java主流框架入门-SpringMVC 2.RESTful开发风格

课程笔记&#xff1a;RESTful 开发风格 课程介绍 本节课程介绍 RESTful 开发风格&#xff0c;以及如何在 Spring MVC 中应用这种开发模式。传统 MVC 开发通过 Servlet、JSP 和 Java Bean 实现前后端交互&#xff0c;而 RESTful 开发提供了一种新的理念&#xff0c;更适合现代…...

QT枚举类型转字符串和使用QDebug<<重载输出私有枚举类型

一 将QT自带的枚举类型转换为QString 需要的头文件&#xff1a; #include <QMetaObject> #include <QMetaEnum> 测试代码 const QMetaObject *metaObject &QImage::staticMetaObject;QMetaEnum metaEnum metaObject->enumerator(metaObject->indexOf…...

手机柔性屏全贴合视觉应用

在高科技日新月异的今天&#xff0c;手机柔性显示屏作为智能手机市场的新宠&#xff0c;以其独特的可弯曲、轻薄及高耐用性特性引领着行业潮流。然而&#xff0c;在利用贴合机加工这些先进显示屏的过程中&#xff0c;仍面临着诸多技术挑战。其中&#xff0c;高精度对位、应力控…...

《Python游戏编程入门》注-第3章3

《Python游戏编程入门》的“3.2.4 Mad Lib”中介绍了一个名为“Mad Lib”游戏的编写方法。 1 游戏玩法 “Mad Lib”游戏由玩家根据提示输入一些信息&#xff0c;例如男人姓名、女人姓名、喜欢的食物以及太空船的名字等。游戏根据玩家输入的信息编写出一个故事&#xff0c;如图…...

Netty-TCP服务端粘包、拆包问题(两种格式)

前言 最近公司搞了个小业务&#xff0c;需要使用TCP协议&#xff0c;我这边负责服务端。客户端是某个设备&#xff0c;客户端传参格式、包头包尾等都是固定的&#xff0c;不可改变&#xff0c;而且还有个蓝牙传感器&#xff0c;透传数据到这个设备&#xff0c;然后通过这个设备…...

centos安装指定版本的jenkins

打开jenkins镜像包官网&#xff0c;找到自己想要安装的版本&#xff0c;官网地址&#xff1a;https://mirrors.tuna.tsinghua.edu.cn/jenkins/redhat-stable 下载指定版本安装包&#xff1a; wget https://mirrors.tuna.tsinghua.edu.cn/jenkins/redhat-stable/jenkins-2.452.…...

QT 周期性的杀死一个进程(软件),一分钟后自动退出

1.原因&#xff1a;某软件开机自启动很烦&#xff0c;搞一个程序干掉这个自启动的软件 2.QT代码 main.cpp #include "KillXXX.h" #include <QtWidgets/QApplication>int main(int argc, char *argv[]) {QApplication a(argc, argv);KillXXX k;return a.exec…...

MySQL任意版本安装卸载和数据库原理图绘制

MYSQL任意版本安装和卸载 安装&#xff1a; 1、解压文件 --- 不能出现中文路径 2、在解压目录&#xff08;安装目录&#xff09;下&#xff1a; 1>.创建data文件夹 2>.创建配置文件my.txt 然后修改成ini格式 3、修改配置文件 basedirD:\\mysql\\mysql-5.7.28-winx64…...

技术成神之路:设计模式(二十三)解释器模式

相关文章&#xff1a;技术成神之路&#xff1a;二十三种设计模式(导航页) 介绍 解释器模式&#xff08;Interpreter Pattern&#xff09;是一种行为设计模式&#xff0c;用于定义一种语言的文法表示&#xff0c;并提供一个解释器来处理这种文法。它用于处理具有特定语法或表达…...

2024软考《软件设计师》-Python专题知识(含历年真题解析)

自2020年之后&#xff0c;软考软件设计师考试在综合知识部分开始增加Python编程语言相关考点&#xff0c;每年会考2~3分的样子。本文将结合近几年常考的内容&#xff0c;扩展一下Pyhton的基础知识&#xff01;考前看一看&#xff0c;或许有所帮助。 一、基础语法 标识符 第一…...

基于大数据 Python+Vue 旅游推荐可视化系统(源码+LW+部署讲解+数据库+ppt)

&#xff01;&#xff01;&#xff01;&#xff01;&#xff01;&#xff01;&#xff01;&#xff01;&#xff01; 会持续一直更新下去 有问必答 一键收藏关注不迷路 源码获取&#xff1a;https://pan.baidu.com/s/1aRpOv3f2sdtVYOogQjb8jg?pwdjf1d 提取码: jf1d &#…...

使用虚拟机搭建环境:CentOS7 Docker、MySQL、Redis 安装与配置

创作灵感 项目实践总结&#xff1a;记录了在虚拟机中安装与配置CentOS7环境下的Docker、MySQL、Redis的全过程&#xff0c;帮助理解和应用各项技术。技术笔记与问题总结&#xff1a;详细梳理了每一步安装的关键点与常见问题&#xff0c;并给出了解决方案。职业感悟与心得&…...

[分享] Docker容器可视化管理工具 - WGCLOUD

WGCLOUD是新一代运维监测平台&#xff0c;它可以监控Docker容器的各种性能数据&#xff0c;比如内存&#xff0c;cpu&#xff0c;Image&#xff0c;运行时间&#xff0c;运行状态&#xff0c;端口映射等信息 WGCLOUD也支持在页面启动&#xff0c;重启&#xff0c;停止Docker容…...

保存网页中 canvas 的内容

在开发人员工具中,保存网页中 canvas 的内容,可以用这个方法: 1. 在 dom 中创建一个下载按钮 <button id="save">保存</button>2. 控制台中运行: const gCanvas = document.querySelector(#page_1);function onSave() {gCanvas.toBlob((blob) =&g…...

React第五十七节 Router中RouterProvider使用详解及注意事项

前言 在 React Router v6.4 中&#xff0c;RouterProvider 是一个核心组件&#xff0c;用于提供基于数据路由&#xff08;data routers&#xff09;的新型路由方案。 它替代了传统的 <BrowserRouter>&#xff0c;支持更强大的数据加载和操作功能&#xff08;如 loader 和…...

什么是库存周转?如何用进销存系统提高库存周转率?

你可能听说过这样一句话&#xff1a; “利润不是赚出来的&#xff0c;是管出来的。” 尤其是在制造业、批发零售、电商这类“货堆成山”的行业&#xff0c;很多企业看着销售不错&#xff0c;账上却没钱、利润也不见了&#xff0c;一翻库存才发现&#xff1a; 一堆卖不动的旧货…...

今日科技热点速览

&#x1f525; 今日科技热点速览 &#x1f3ae; 任天堂Switch 2 正式发售 任天堂新一代游戏主机 Switch 2 今日正式上线发售&#xff0c;主打更强图形性能与沉浸式体验&#xff0c;支持多模态交互&#xff0c;受到全球玩家热捧 。 &#x1f916; 人工智能持续突破 DeepSeek-R1&…...

OpenPrompt 和直接对提示词的嵌入向量进行训练有什么区别

OpenPrompt 和直接对提示词的嵌入向量进行训练有什么区别 直接训练提示词嵌入向量的核心区别 您提到的代码: prompt_embedding = initial_embedding.clone().requires_grad_(True) optimizer = torch.optim.Adam([prompt_embedding...

大语言模型(LLM)中的KV缓存压缩与动态稀疏注意力机制设计

随着大语言模型&#xff08;LLM&#xff09;参数规模的增长&#xff0c;推理阶段的内存占用和计算复杂度成为核心挑战。传统注意力机制的计算复杂度随序列长度呈二次方增长&#xff0c;而KV缓存的内存消耗可能高达数十GB&#xff08;例如Llama2-7B处理100K token时需50GB内存&a…...

Mysql中select查询语句的执行过程

目录 1、介绍 1.1、组件介绍 1.2、Sql执行顺序 2、执行流程 2.1. 连接与认证 2.2. 查询缓存 2.3. 语法解析&#xff08;Parser&#xff09; 2.4、执行sql 1. 预处理&#xff08;Preprocessor&#xff09; 2. 查询优化器&#xff08;Optimizer&#xff09; 3. 执行器…...

云原生安全实战:API网关Kong的鉴权与限流详解

&#x1f525;「炎码工坊」技术弹药已装填&#xff01; 点击关注 → 解锁工业级干货【工具实测|项目避坑|源码燃烧指南】 一、基础概念 1. API网关&#xff08;API Gateway&#xff09; API网关是微服务架构中的核心组件&#xff0c;负责统一管理所有API的流量入口。它像一座…...

python爬虫——气象数据爬取

一、导入库与全局配置 python 运行 import json import datetime import time import requests from sqlalchemy import create_engine import csv import pandas as pd作用&#xff1a; 引入数据解析、网络请求、时间处理、数据库操作等所需库。requests&#xff1a;发送 …...

从面试角度回答Android中ContentProvider启动原理

Android中ContentProvider原理的面试角度解析&#xff0c;分为​​已启动​​和​​未启动​​两种场景&#xff1a; 一、ContentProvider已启动的情况 1. ​​核心流程​​ ​​触发条件​​&#xff1a;当其他组件&#xff08;如Activity、Service&#xff09;通过ContentR…...

嵌入式常见 CPU 架构

架构类型架构厂商芯片厂商典型芯片特点与应用场景PICRISC (8/16 位)MicrochipMicrochipPIC16F877A、PIC18F4550简化指令集&#xff0c;单周期执行&#xff1b;低功耗、CIP 独立外设&#xff1b;用于家电、小电机控制、安防面板等嵌入式场景8051CISC (8 位)Intel&#xff08;原始…...