位图用位存储布尔状态，C++中通过位运算高效实现，以字节数组为底层存储，每bit代表一个整数是否存在，支持set、clear、test操作，节省内存至N/8字节。
位图（Bitmap）是一种用单个位来存储信息的数据结构，适合处理大量布尔状态的场景，比如去重、排序、布隆过滤器等。C++中通过位运算和空间优化可以高效实现一个轻量级的 Bitmap。
基本原理与设计思路
一个 bit 可以表示 0 或 1 状态，如果我们想记录 N 个整数是否存在，传统数组需要 N 字节，而位图只需 N/8 字节（向下取整并加一），大幅节省内存。
核心思想是：用一个字节数组（或整型数组）作为底层存储，每个 bit 代表一个整数是否出现过。例如第 i 个 bit 为 1 表示整数 i 存在。
关键操作：
立即学习“C++免费学习笔记（深入）”；
set(i)：将第 i 位置 1clear(i)：将第 i 位置 0test(i)：查询第 i 位是否为 1
位运算实现细节
使用位运算对指定位置进行操作。假设我们有一个 unsigned char 数组，要操作第 i 位：
确定该位所在的字节下标：i / 8 或 i >> 3确定在字节内的偏移量：i % 8 或 i & 7设置某一位：使用按位或 |= (1 清除某一位：使用按位与 &= ~(1 测试某一位：使用按位与判断结果是否非零
代码示例：
class Bitmap {private: std::vector data; size_t n_bits;public:explicit Bitmap(size_t bits) : n_bits(bits) {data.resize((bits + 7) / 8, 0); // 向上取整}
void set(size_t i) { if (i >= n_bits) return; size_t byte_idx = i >> 3; size_t offset = i & 7; data[byte_idx] |= (1U <= n_bits) return; size_t byte_idx = i >> 3; size_t offset = i & 7; data[byte_idx] &= ~(1U <= n_bits) return false; size_t byte_idx = i >> 3; size_t offset = i & 7; return (data[byte_idx] & (1U << offset)) != 0;}
};
空间优化技巧
为了进一步提升性能和减少内存占用，可以考虑以下几点：
使用 uint32_t 或 uint64_t 替代 unsigned char 数组，减少边界检查次数，提高缓存命中率采用模板参数指定元素类型，实现通用性预分配足够空间避免频繁扩容批量操作时可用“平行位”技术或内置函数如 __builtin_popcount 统计 1 的个数
进阶版使用 uint32_t 数组的例子：
templateclass FastBitmap { static constexpr int BITS_PER_BLOCK = sizeof(Block) * 8; std::vector data; size_t n_bits;public:explicit FastBitmap(size_t bits) : n_bits(bits) {data.resize((bits + BITS_PER_BLOCK - 1) / BITS_PER_BLOCK, 0);}
void set(size_t i) { if (i >= n_bits) return; size_t block = i / BITS_PER_BLOCK; size_t offset = i % BITS_PER_BLOCK; data[block] |= (Block(1) <= n_bits) return false; size_t block = i / BITS_PER_BLOCK; size_t offset = i % BITS_PER_BLOCK; return (data[block] & (Block(1) <= n_bits) return; size_t block = i / BITS_PER_BLOCK; size_t offset = i % BITS_PER_BLOCK; data[block] &= ~(Block(1) << offset);}
};
应用场景与注意事项
Bitmap 常用于：
快速去重（如统计 1~100 万中出现过的数字）内存敏感的索引结构配合哈希实现布隆过滤器操作系统中的页分配管理
注意点：
只适用于整数范围有限的场景（比如 0~几千万）不支持负数（除非做偏移映射）稀疏数据可能浪费空间，此时可考虑 Roaring Bitmap线程安全需外部保证，必要时加锁或使用原子操作
基本上就这些。掌握位运算和内存布局，就能写出高效简洁的位图实现。
以上就是c++++怎么实现一个位图(Bitmap)数据结构_c++位运算与空间优化实现的详细内容，更多请关注创想鸟其它相关文章！
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如发现本站有涉嫌抄袭侵权/违法违规的内容， 请发送邮件至 chuangxiangniao@163.com 举报，一经查实，本站将立刻删除。
发布者：程序猿，转转请注明出处：https://www.chuangxiangniao.com/p/1484579.html
微信扫一扫 
支付宝扫一扫 
