位图通过位操作高效管理布尔状态，使用std::vector按位存储，支持set、reset、get操作，适用于去重、排序等场景，空间时间效率优于集合容器。
位图（Bitmap）是一种高效的数据结构，用来表示一组布尔值（0 或 1），常用于快速标记和查询某个元素是否存在。在 C++ 中，可以通过 std::vector 或手动使用整型数组配合位操作来实现一个简单的位图。下面介绍一种基于位操作的自定义位图实现。
基本原理
位图的核心思想是：用一个 bit 来表示一个整数的状态（比如是否存在）。假设我们要管理 0 到 N-1 的整数，那么只需要 (N + 31) / 32 个 32 位整数（即 unsigned int）即可存储所有状态。
每个 bit 对应一个整数：
bit[i] = 1 表示整数 i 存在 bit[i] = 0 表示整数 i 不存在
通过位运算可以高效地进行设置、清除和查询操作。
立即学习“C++免费学习笔记（深入）”；
关键位操作
要实现位图，需要掌握三个基本操作：
确定所在整数位置：index / 32 → index >> 5 确定在该整数中的 bit 位置：index % 32 → index & 0x1F 设置某一位为 1：bits[i >> 5] |= (1U 设置某一位为 0：bits[i >> 5] &= ~(1U 查询某一位是否为 1：(bits[i >> 5] & (1U
简单 Bitmap 类实现
#include #include class Bitmap {private: std::vector bits; size_t size;public: // 构造函数：指定最大处理的数值范围 [0, n) Bitmap(size_t n) : size(n) { bits.resize((n + 31) / 32, 0); } // 设置第 i 个位为 1 void set(size_t i) { if (i >= size) return; bits[i >> 5] |= (1U <= size) return; bits[i >> 5] &= ~(1U <= size) return false; return (bits[i >> 5] & (1U << (i & 0x1F))) != 0; } // 打印前 n 个位的状态（用于调试） void print(size_t n) { for (size_t i = 0; i < n && i < size; ++i) { std::cout << get(i); } std::cout << std::endl; }};
使用示例
int main() { Bitmap bm(64); // 支持 0~63 bm.set(10); bm.set(20); bm.set(31); std::cout << "位状态: "; bm.print(32); // 输出前32位 std::cout << "get(10): " << bm.get(10) << std::endl; // 1 std::cout << "get(15): " << bm.get(15) << std::endl; // 0 bm.reset(10); std::cout << "reset 后 get(10): " << bm.get(10) << std::endl; // 0 return 0;}
这个简单的位图适用于去重、排序（如计数排序变种）、布隆过滤器底层等场景。相比直接使用 std::set 或 std::unordered_set，位图在处理密集整数时空间和时间效率更高。
基本上就这些。理解位操作是关键，实际应用中还可以扩展支持更多功能，比如按位与/或、统计 1 的个数（popcount）等。不复杂但容易忽略边界检查和位运算细节。
以上就是C++如何实现一个简单的位图(Bitmap)_C++数据结构与位图实现的详细内容，更多请关注创想鸟其它相关文章！
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如发现本站有涉嫌抄袭侵权/违法违规的内容， 请发送邮件至 chuangxiangniao@163.com 举报，一经查实，本站将立刻删除。
发布者：程序猿，转转请注明出处：https://www.chuangxiangniao.com/p/1484240.html
微信扫一扫 
支付宝扫一扫 
