C++位图数据结构详解（从零开始实现高效位图Bitmap）

什么是位图？

位图本质上是一个由比特位（bit）组成的数组。每个 bit 代表一个整数是否存在于集合中：1 表示存在，0 表示不存在。例如，如果我们想记录数字 0 到 7 是否出现过，只需一个字节（8 bits）即可：

// 位图示例：记录 0~7 的存在状态// bit[0] = 1 → 数字 0 存在// bit[3] = 1 → 数字 3 存在// bit[5] = 0 → 数字 5 不存在位图字节：10100101对应数字：76543210

这种设计极大地节省了内存。相比用 bool 数组（每个 bool 通常占 1 字节），位图可节省 8 倍空间！

C++位图数据结构实现步骤

我们将实现一个支持以下功能的 Bitmap 类：

• set(int num)：标记某个数字存在
• unset(int num)：取消标记
• test(int num)：检查数字是否存在
• 自动扩展容量（可选）

1. 确定存储方式

C++ 中没有直接操作单个 bit 的类型，但我们可以通过 std::vector<unsigned char> 或 std::vector<uint64_t> 来模拟。这里我们使用 std::vector<uint64_t>，因为现代 CPU 对 64 位操作更高效。

2. 核心逻辑：位运算

要操作第 n 位，我们需要：

• 确定它在哪个 uint64_t 元素中：index = n / 64
• 确定它在该元素中的偏移：offset = n % 64
• 使用位运算设置/清除/测试该位

完整代码实现

#include <iostream>#include <vector>#include <cstdint>class Bitmap {private:    std::vector<uint64_t> data;    size_t max_num;public:    // 构造函数：指定最大支持的数字    explicit Bitmap(size_t max_value) : max_num(max_value) {        size_t num_words = (max_value + 63) / 64; // 向上取整        data.resize(num_words, 0);    }    // 设置某一位为1    void set(size_t num) {        if (num > max_num) return; // 超出范围        size_t index = num / 64;        size_t offset = num % 64;        data[index] |= (1ULL << offset);    }    // 设置某一位为0    void unset(size_t num) {        if (num > max_num) return;        size_t index = num / 64;        size_t offset = num % 64;        data[index] &= ~(1ULL << offset);    }    // 测试某一位是否为1    bool test(size_t num) const {        if (num > max_num) return false;        size_t index = num / 64;        size_t offset = num % 64;        return (data[index] & (1ULL << offset)) != 0;    }};// 使用示例int main() {    Bitmap bm(1000); // 支持 0~1000 的整数    bm.set(10);    bm.set(100);    std::cout << "10 exists? " << bm.test(10) << std::endl;   // 输出 1    std::cout << "50 exists? " << bm.test(50) << std::endl;   // 输出 0    std::cout << "100 exists? " << bm.test(100) << std::endl; // 输出 1    bm.unset(10);    std::cout << "10 after unset: " << bm.test(10) << std::endl; // 输出 0    return 0;}

关键点解析

• 1ULL << offset：使用无符号长整型（64位）确保左移不会溢出
• 向上取整计算数组大小：`(max_value + 63) / 64` 是常用技巧
• 边界检查：防止访问越界

应用场景

C++位图数据结构广泛应用于：

• 数据库索引优化
• 内存高效的集合操作
• 网络爬虫 URL 去重
• 操作系统内存页管理

总结

通过本教程，你已经掌握了如何用 C++语言 实现一个基础但实用的位图数据结构。位图不仅节省内存，而且操作速度极快（O(1) 时间复杂度）。掌握这一技能，对提升算法效率和系统设计能力大有裨益。

如果你正在学习 C++位图操作 或准备面试，建议动手敲一遍代码，并尝试扩展功能（如支持动态扩容、位图交并差运算等）。

希望这篇 位图bitmap C++ 教程对你有所帮助！