位图(C语言版)
文章目录
- 位图
- 模型
- 基本操作
- 实现
- 代码
- 运行结果
- 应用
- 存储只有两种状态的数据
- 排序并去重
位图
模型
位图是“位”的数组。
为什么需要构建一个专门的数据结构来表示位的数组?:因为计算机最小的寻址单位是字节,而不是位。
位图是一种内存紧凑的数据结构,即位图在内存资源紧张的设备中更多使用,如嵌入式设备等。
基本操作
- 增 set:将某一位设置为1
- 删 unset:将某一位设置为0
- 查 isset:判断某一位是不是1
- 遍历
实现
代码
// 位运算技巧
n * 32 等价于 n << 5 /* 2^5 = 32 */
n / 32 等价于 n >> 5
n % 32 等价于 n & 0x1F /* 与31(MASK)相与 */
n |= 0x1 << offset /* 将n的第offset位设置为1 */
n &= ~(0x1 << offset) /* 将n的第offset位设置为0 */
位图要求尽可能少地使用内存空间,所以实际使用多少内存,就申请多少内存。
// BitMap.h
#include <stdbool.h>
#include <stdint.h>typedef uint32_t Word; // uint32_t: 1.大小确定 (32bits); 2.无符号整数typedef struct {Word* array; size_t bits; // 位数组的长度
} BitMap;BitMap* bitmap_create(size_t bits);
void bitmap_destroy(BitMap* bm);void bitmap_set(BitMap* bm, size_t n); // n is a bit index
void bitmap_unset(BitMap* bm, size_t n);
bool bitmap_isset(BitMap* bm, size_t n);
void bitmap_clear(BitMap* bm);
// BitMap.c
#include "BitMap.h"
#include <stdlib.h>
#include <string.h>
#include <stdio.h>#define BITS_PER_WORD 32
#define BITMAP_SHIFT 5
#define BITMAP_MASK 0x1F
// 存储bits位,需要多少个word
#define BITMAP_SIZE(bits) ((bits + BITS_PER_WORD - 1) >> BITMAP_SHIFT)// 位图的长度
BitMap* bitmap_create(size_t bits) {BitMap* bm = (BitMap*)malloc(sizeof(BitMap));bm->array = (Word*)calloc(BITMAP_SIZE(bits), BITS_PER_WORD);bm->bits = bits;return bm;
}void bitmap_destroy(BitMap* bm) {// 1. 释放arrayfree(bm->array);// 2. 释放BitMapfree(bm);
}void grow_capacity(BitMap* bm, size_t bits) {Word* newArray = (Word*)realloc(bm->array, BITMAP_SIZE(bits) * sizeof(Word));bm->array = newArray;// realloc 并不会自动将扩容的空间清零,需要手动清零int bytes = (BITMAP_SIZE(bits) - BITMAP_SIZE(bm->bits)) * sizeof(Word);memset(bm->array + BITMAP_SIZE(bm->bits), 0, bytes);
}void bitmap_set(BitMap* bm, size_t n) { // n is a bit index// 需判断索引n是否在位图范围内if (n + 1 > bm->bits) { // 这里不一定要扩容,但要改变bm->bitsif (BITMAP_SIZE(n + 1) > BITMAP_SIZE(bm->bits)) { // 不在BitMap范围内,需扩容// 扩容grow_capacity(bm, n + 1);}bm->bits = n + 1;}// 如何表示第n位(word, offset)size_t word = n >> BITMAP_SHIFT; // 该索引在哪个word块中size_t offset = n & BITMAP_MASK; // 等价于 n % BITS_PER_WORD (取余操作),表示该索引在该word块的offset位bm->array[word] |= (0x01 << offset);
}void bitmap_unset(BitMap* bm, size_t n) {// 需判断索引n是否在位图范围内if (n + 1 > bm->bits) { // 这里不一定要扩容,但要改变bm->bitsif (BITMAP_SIZE(n + 1) > BITMAP_SIZE(bm->bits)) { // 不在BitMap范围内,需扩容// 扩容grow_capacity(bm, n + 1);}bm->bits = n + 1;}// 如何表示第n位(word, offset)size_t word = n >> BITMAP_SHIFT; // 该索引在哪个word块中size_t offset = n & BITMAP_MASK; // 等价于 n % BITS_PER_WORD (取余操作),表示该索引在该word块的offset位bm->array[word] &= ~(0x01 << offset);
}bool bitmap_isset(BitMap* bm, size_t n) {// 需判断索引n是否在位图范围内if (n + 1 > bm->bits) {printf("索引n不在位图范围内\n");return false;}// 如何表示第n位(word, offset)size_t word = n >> BITMAP_SHIFT; // 该索引在哪个word块中size_t offset = n & BITMAP_MASK; // 等价于 n % BITS_PER_WORD (取余操作),表示该索引在该word块的offset位return bm->array[word] & (0x1 << offset);
}void bitmap_clear(BitMap* bm) {// 全部置零int bytes = BITMAP_SIZE(bm->bits) * sizeof(Word);memset(bm->array, 0, bytes);
}
// main.c
#include <stdio.h>
#include "BitMap.h"int main() {BitMap* bm = bitmap_create(100);int bits_per_word = 8 * sizeof(bm->array[0]);printf("位图使用了%d 位的空间,实际开辟的内存空间%d\n", bm->bits, bits_per_word * (1 + bm->bits / bits_per_word));bitmap_set(bm, 80);printf("第80位的值为:%d\n", bitmap_isset(bm, 80));bitmap_unset(bm, 80);printf("第80位的值为:%d\n", bitmap_isset(bm, 80));bitmap_set(bm, 130); // 扩容printf("位图使用了%d 位空间,实际开辟的内存空间%d\n", bm->bits, bits_per_word * (1 + bm->bits / bits_per_word));bitmap_clear(bm);printf("第0~50位的值为:");for (int i = 0; i < 50; i++) {printf(" %d", bitmap_isset(bm, i));}bitmap_destroy(bm);return 0;
}
运行结果
应用
存储只有两种状态的数据
比如,存储10亿 ( 1 0 9 ≈ 2 30 10^{9} \approx 2^{30} 109≈230) QQ用户的在线状态:
- 如果用int数组存储,那么需要的存储空间为:
4B * 2^30 = 4GB
- 如果用位图存储,所需空间位:
1/8B * 2^30 = 0.125GB
排序并去重
比如排序数组int array[] = {123, 456, 3, 7, 8, 9, 34, 3, 7, 3};
并去重
- 如果用平常方法:需要先对数组进行排序(快速排序O(nlog(n)),然后对排序后的数组去重 (O(n))
- 使用位图,可以将数组array的值对应为位图的位索引, 比如数组第一个值为123, 那么就将位图索引为128的位设置为1,对其他数组值也进行相同处理。最后输出位图中值为1的位对应索引即可。时间复杂度为O(n)
相关文章:

位图(C语言版)
文章目录 位图模型基本操作实现代码运行结果 应用存储只有两种状态的数据排序并去重 位图 模型 位图是“位”的数组。 为什么需要构建一个专门的数据结构来表示位的数组?:因为计算机最小的寻址单位是字节,而不是位。 位图是一种内存紧凑的…...

使用C#元组实现列表分组汇总拼接字段
文章目录 使用C#元组实现列表分组汇总拼接字段代码运行结果 使用C#元组实现列表分组汇总拼接字段 代码 string message string.empty; var tupleList new List<Tuple<string, string, string>>(); tupleList.Add(new Tuple<string, string, string>("…...

淘宝API数据采集接口||调用步骤详解
### 一、注册与认证 1. **注册淘宝开发者账号**: * 访问淘宝开放平台官网,点击“立即入驻”按钮,按照提示完成注册流程。注册过程中需要提供企业名称、联系人信息等基本信息。 2. **创建应用**: * 注册成功后,登录淘…...

C# 调用 C++ 动态库接口
在 C# 中调用 C 动态库接口,通常需要通过 P/Invoke (Platform Invocation Services) 来与 C 代码交互 1. 准备 C 动态库 假设你有一个 C 动态库,其中包含如下函数: extern "C" char* getLocationURL(const char* package_name, …...

fastadmin 接口请求提示跨域
问题描述 小程序项目,内嵌h5页面,在h5页面调用后端php接口,提示跨域。网上查找解决方案如下: 1,设置header // 在入口文件index.php直接写入直接写入 header("Access-Control-Allow-Origin:*"); header(&q…...

C#_文件写入读取操作
文件写入操作:--------------------------------------------------------------------------- 读取文件:---------------------------------------------------------------------------...

redis的哨兵模式和集群模式
Redis 的 哨兵模式(Sentinel Mode) 和 集群模式(Cluster Mode) 是两种常见的高可用部署方式,它们各有优缺点,适用于不同的场景。以下是它们的比较: 1. 哨兵模式(Sentinel Mode&#…...

《open3d +pyqt》凸包计算
《open3d +pyqt》凸包计算 一、效果展示二、qt设置2.1界面设置2.2 py文件生成三、核心代码一、效果展示 二、qt设置 2.1界面设置 添加动作Qhull: 布局参数: 2.2 py文件生成 更新Mainwindow.py 生成py文件 三、核心代码 代码如下: main.py文件...

数据库报错1045-Access denied for user ‘root‘@‘localhost‘ (using password: YES)解决方式
MySQL 报错 1045 表示用户root从localhost连接时被拒绝访问,通常是因为密码错误、权限问题或配置问题。以下是解决该问题的常见方法: 方法一:检查用户名和密码 • 确认用户名和密码是否正确: 确保输入的用户名和密码完全正确&am…...

ThreadLocal为什么会内存溢出
每个线程(Thread 对象)内部维护一个 ThreadLocalMap,用于存储该线程的所有 ThreadLocal 变量的键值对: ThreadLocalMap虽然是ThreadLocal的静态内部类,但是Thread 对象的属性,当线程存活时ThreadLocalMap不会被回收。 Key:ThreadLocal 实例的 弱引用(WeakReference)。…...

数据结构------单向链表。
一.实现单向链表的头插,头删,尾插,尾删,按位置插,按位置删,按位置修改,按元素查找,按元素修改,按元素删除,单链表的逆置,查找倒数第几个元素&…...

Python的那些事第二十二篇:基于 Python 的 Django 框架在 Web 开发中的应用研究
基于 Python 的 Django 框架在 Web 开发中的应用研究 摘要 Django 是一个基于 Python 的高级 Web 框架,以其开发效率高、安全性和可扩展性强等特点被广泛应用于现代 Web 开发。本文首先介绍了 Django 的基本架构和核心特性,然后通过一个实际的 Web 开发项目案例,展示了 Dj…...

在 PyCharm 中接入deepseek的API的各种方法
在 PyCharm 中接入 DeepSeek 的 API,通常需要以下步骤: 1. 获取 DeepSeek API 密钥 首先,确保你已经在 DeepSeek 平台上注册并获取了 API 密钥(API Key)。如果没有,请访问 DeepSeek 的官方网站注册并申请 …...

当扩展屏显示【输入不支持】怎么解决?!
1、why? 当你遇到这个问题的时候,那就表示您的扩展屏偏老旧,这时候需要进行一些参数设置 2、直接改变桌面模式解决不了问题 你是不是尝试过直接在缩放和布局这里设置?在这里直接设置的话,设置的是桌面模式,屏幕大小是会变化但…...

深入剖析 Python 类属性与对象的底层创建与内存分析
各类资料学习下载合集 https://pan.quark.cn/s/8c91ccb5a474 在 Python 中,类和对象是面向对象编程(OOP)的核心组成部分。类属性与实例属性的存储和管理方式,以及类和对象在内存中的分布和结构,对于深入理解 Python 的底层机制至关重要。 本文将带你详细解析 P…...

pdf文件的读取,基于深度学习的方法
需要安装一些依赖解析 PDF 文件的详细指南_unstructured.partition.pdf-CSDN博客文章浏览阅读1.3k次,点赞13次,收藏9次。通过 unstructured.partition.pdf 函数,可以方便地解析 PDF 文件并提取其中的文本和表格内容。尽管在使用过程中可能会遇…...

【指令集】Nginx
本文作者: slience_me 【指令集】Nginx 1. 目录结构 Nginx 的基础目录结构通常包括以下几个主要目录: Nginx的目录结构大致如下(以Linux系统为例): /etc/nginx/ # Nginx的配置文件目录 ├── ngin…...

蓝耘云智算|使用 Deepseek R1 模型优化 BERT 在 NLP 任务中的表现
在自然语言处理(NLP)领域,BERT(Bidirectional Encoder Representations from Transformers)已成为许多文本分类任务的基准模型。然而,随着新模型的出现和技术的不断进步,BERT在某些情况下可能不…...

LINUX常用命令学习
查看系统版本 使用hostnamectl命令检查。hostnamectl显示了CentOS的版本以及操作系统的相关信息,非常方便 设置linux机器别名称 hostnamectl set-hostname 机器别名 --static 华为云 centos 命令:lsb_release -a linux:cat /proc/version 查看进程路…...

【java面向对象的三大特性】封装、继承和多态
目录标题 一、封装(Encapsulation):二、继承(Inheritance):三、多态(Polymorphism):1. 多态的三个必要条件:2.多态的具体实现:3.多态的使用场景&a…...

【开源免费】基于SpringBoot+Vue.JS校园商铺管理系统(JAVA毕业设计)
本文项目编号 T 191 ,文末自助获取源码 \color{red}{T191,文末自助获取源码} T191,文末自助获取源码 目录 一、系统介绍二、数据库设计三、配套教程3.1 启动教程3.2 讲解视频3.3 二次开发教程 四、功能截图五、文案资料5.1 选题背景5.2 国内…...

日常故障排查 - Java程序故障排查
Java程序故障 无论对于任何的故障而言,恢复可用性都是首要目标。但作为一个技术匠人,不能让同一个问题导致多次故障,因此故障的根因剖析以及解决也是很重要的。但是故障根因剖析是需要现场数据来进行分析,因此在故障恢复之前要尽…...

ai数字人分身系统开发源码saas化
#数字人分身系统# #数字人系统源码# #ai数字人123 123# 云罗抖去推数字人分身系统是一款融合了形象克隆、声音克隆、AI数字人分身、AI智能剪辑、智能文案等各种AI技术一体化的短视频营销工具,其核心功能优势主要体现在以下几方面: 真实度高…...

DeepSeek免费部署到WPS或Office
部署到WPS - 通过OfficeAI插件接入: - 准备工作:安装最新版本的WPS Office软件;访问DeepSeek官网,点击右上角的“API开放平台”,登录账号(若无账号需先注册),登录成功后,…...

vue2和vue3插槽slot最通俗易懂的区别理解
在 Vue 的组件通信中,slot(插槽)的编译优化是一个重要的性能提升点。以下是 Vue2 和 Vue3 在 slot 处理上的差异及优化原理,用更直观的方式解释: Vue2 的 Slot 更新机制 想象一个父子组件场景: 父组件&am…...

生成式人工智能:技术革命与应用图景
(这文章有些地方看不懂很正常,因为有太多生词,需要对 计算机/人工智能 研究至深的人才能看懂,遇到不会的地方用浏览器搜索或跳过) 引言 2023年被称我们为"生成式AI元年",以GPT-4、DALL-E 3、Stable Diffusi…...

关于Dest1ny:我的创作纪念日
Dest1ny 因为这是csdn任务,我就稍微“写”了一下! 如果大家真的有什么想聊的或者想一起学习的,欢迎在评论区或者私信中与我讨论! 2025想说的话 我就把我想说的写在前面! 不用对未来焦虑,不要觉得自己走…...

AI学习记录 - 最简单的专家模型 MOE
代码 import torch import torch.nn as nn import torch.nn.functional as F from typing import Tupleclass BasicExpert(nn.Module):# 一个 Expert 可以是一个最简单的, linear 层即可# 也可以是 MLP 层# 也可以是 更复杂的 MLP 层(active function 设…...

【C++内存管理】—— 策略、陷阱及应对之道
欢迎来到ZyyOvO的博客✨,一个关于探索技术的角落,记录学习的点滴📖,分享实用的技巧🛠️,偶尔还有一些奇思妙想💡 本文由ZyyOvO原创✍️,感谢支持❤️!请尊重原创…...

分布式版本控制系统---git
Git:从基础到进阶的全面指南 Git 是一个分布式版本控制系统,广泛应用于软件开发中,用于跟踪文件的更改、支持团队协作以及管理项目代码。通过 Git,开发者可以在本地拥有完整的项目历史记录,进行离线开发,并…...

pg_sql关于时间的函数
1、时间戳和日期之间的相互转换 时间戳转日期(时间戳为数值类型,若为字符型需进行转换) # 保留到秒:2025-10-02 04:46:40 (字符型转换数值型) select to_timestamp(1759351600::bigint)# 保留到日&#x…...

【Kafka】Windows下安装Kafka(全面)
目录 1.前提条件 2.下载 3.安装 4.环境变量配置 5.验证 1.前提条件 参考版本:zookeeper为3.6.4 kafka版本为3.5.1 1.先安装zookeeper: 【Zookeeper】Windows下安装Zookeeper(全面)-CSDN博客https://blog.csdn.net/…...

【Qt】:概述(下载安装、认识 QT Creator)
🌈 个人主页:Zfox_ 🔥 系列专栏:Qt 目录 一:🔥 介绍 🦋 什么是 QT🦋 QT 发展史🦋 Qt版本🦋 QT 优点 一:🔥 搭建Qt开发环境 ǹ…...

Netty源码解析之异步处理(二):盛赞Promise中的集合设计
前言 在阅读Netty源码的过程中,我越来越相信一句话:“Netty的源码非常好,质量极高,是Java中质量最高的开源项目之一”。如果认真研究,会有一种遍地黄金的感觉。 本篇文件我将记录一下鄙人在Promise的实现类DefaultPr…...

Spring Boot 的约定优于配置,你的理解是什么?
“约定优于配置” 是 Spring Boot 极为重要的设计理念,它极大地简化了 Spring 应用的开发流程,下面从多个方面详细解释这一理念: 减少配置复杂性 传统开发的痛点 在传统的 Spring 开发里,配置工作相当繁琐。以配置 Spring MVC …...

图形渲染(一)——Skia、OpenGL、Mesa 和 Vulkan简介
1.Skia —— 2D 图形库 Skia 是一个 2D 图形库,它的作用是为开发者提供一个高层次的绘图接口,方便他们进行 2D 图形渲染(比如绘制文本、形状、图像等)。Skia 本身不直接管理 GPU 或进行底层的渲染工作,而是通过 底层图…...

git使用,注意空格
第一节 安装完成后,找个目录用于存储,打开目录右击选择git bash here 命令1 姓名 回车 git config --global user.name "li" 命令2 邮箱 回车 git config --global user.email "888163.com" 命令3 初始化新仓库,下载克隆 回…...

以用户为中心,汽车 HMI 界面设计的创新之道
在汽车智能化飞速发展的当下,汽车 HMI(人机交互界面)成为连接人与车的关键桥梁。如何打造出优秀的 HMI 界面?答案是以用户为中心,探索创新之道。 用户需求是汽车 HMI 界面设计的指南针。在设计前期,深入调…...

CentOS安装Docker,Ubuntu安装Docker,Docker解决方案
文章目录 CentOS7安装DockerUbuntu修改Docker镜像源docker设置容器自动启动启动时加--restartalways如果已经过运行的项目docker compose设置容器自启动 docker file修改时区docker在容器执行命令简单粗暴的办法安装curl docker compose命令安装docker compose Docker WEB 图形…...

c#中“事件-event”的经典示例与理解
在C#编程语言中,事件(Event)是一个非常重要的概念,它提供了一种松耦合的方式,让对象间能够通知彼此,而无需直接联系。事件的使用可以让我们的代码更加灵活、可扩展且易于维护。 事件可以视作委托的实例&…...

git bash在github的库中上传或更新本地文件
一、将本地文件上传到 GitHub 仓库 1. 创建 GitHub 仓库 如果你还没有在 GitHub 上创建仓库,首先需要创建一个新的仓库: 登录到 GitHub。点击右上角的 按钮,选择 New repository。给你的仓库起个名字,并选择 Public 或 Privat…...

【编程实践】vscode+pyside6环境部署
1 PySide6简介 PySide6是Qt for Python的官方版本,支持Qt6,提供Python访问Qt框架的接口。优点包括官方支持、LGPL许可,便于商业应用,与Qt6同步更新,支持最新特性。缺点是相比PyQt5,社区资源较少。未来发展…...

vue 文件下载(导出)excel的方法
目前有一个到处功能的需求,这是我用过DeepSeek生成的导出(下载)excel的一个方法。 1.excel的文件名是后端生成的,放在了响应头那里。 2.这里也可以自己制定文件名。 3.axios用的是原生的axios,不要用处理过的ÿ…...

服务器延迟给视频网站造成的影响
在数字化时代中,网络视频已经成为人们日常娱乐和获取信息的重要平台,网络视频的流畅性会影响着用户的体验度,那么,当服务器出现延迟会对视频网站造成哪些影响呢?本文就来共同了解一下吧! 当所使用的服务器由…...

django上传文件
1、settings.py配置 # 静态文件配置 STATIC_URL /static/ STATICFILES_DIRS [BASE_DIR /static, ]上传文件 # 定义一个视图函数,该函数接收一个 request 参数 from django.shortcuts import render # 必备引入 import json from django.views.decorators.http i…...

Mysql数据库
一.数据定义语言DDL 一.概述 DDL用于定义和管理数据库的结构 DDL关键字:1.CREATE; 2.ALTER; 3.DROP 二.SQL命名规定和规范 1.标识符命名规则 2.标识符命名规范 三.库管理 1. CREATE DATABASE 数据库名; 2. CREATE DATABASE IF NOT EXISTS 数据库名; 3. CREATE…...

机器学习 - 大数定律、可能近似正确学习理论
一、大数定律: 大数定律是概率论中的一个基本定理,其核心思想是:当独立重复的随机试验次数足够大时,样本的平均值会趋近于该随机变量的期望值。下面从直观和数学两个角度来说明这一概念: 1. 直观理解 重复试验的稳定…...

Kotlin 2.1.0 入门教程(十七)接口
接口 接口可以包含抽象方法的声明,也可以包含方法的实现。 接口与抽象类的不同之处在于,接口无法存储状态。接口可以拥有属性,但这些属性要么必须是抽象的,要么就得提供访问器的实现。 接口使用 interface 关键字来定义&#x…...

USB Flash闪存驱动器安全分析(第一部分)
翻译原文链接:Hacking Some More Secure USB Flash Drives (Part I) | SySS Tech Blog 文章翻译总结:文章对一些具有AES硬件加密的USB闪存驱动器的网络安全分析研究。研究由SySS的IT安全专家Matthias Deeg进行,他在2022年初发现了几个安全漏…...

报名丨Computer useVoice Agent :使用 TEN 搭建你的 Mac Assistant
与 TEN 相聚在「LET’S VISION 2025」大会,欢迎来展位上跟我们交流。这次我们还准备了一场聚焦「computer use」的工作坊,功能新鲜上线,线下首波体验! 📅 TEN 展位:2025年3月1日-2日 TEN workshop&#x…...