C++如何实现一个简单的位图(Bitmap)_C++数据结构与位图实现

下次还敢 2025-11-16 00:00:00 次阅读

位图通过位操作高效管理布尔状态，使用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 不存在

通过位运算可以高效地进行设置、清除和查询操作。

关键位操作

要实现位图，需要掌握三个基本操作：

确定所在整数位置：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 << (i & 0x1F));
    }

    // 将第 i 个位清零
    void reset(size_t i) {
        if (i >= size) return;
        bits[i >> 5] &= ~(1U << (i & 0x1F));
    }

    // 查询第 i 个位是否为 1
    bool get(size_t i) const {
        if (i >= 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）等。不复杂但容易忽略边界检查和位运算细节。