C++怎么实现一个位图(Bitmap)_C++海量数据处理与空间优化技巧-C++-PHP中文网

C++怎么实现一个位图(Bitmap)_C++海量数据处理与空间优化技巧

冰火之心

发布： 2025-12-12 11:03:22

原创

306人浏览过

位图是一种高效数据结构，通过比特数组表示非负整数的存在状态，显著节省内存。例如，表示1千万个整数仅需约1.2MB，远低于传统方法的40MB。文章给出了C++实现，包含设置、清除、查询和翻转操作，利用uint32_t数组按位操作，支持去重、排序和快速查找。应用场景包括活跃用户统计、布隆过滤器及大文件内存映射，还可结合Roaring Bitmap优化。注意事项有：限非负整数、需边界检查、多线程保护和合理预估规模。

c++怎么实现一个位图(bitmap)_c++海量数据处理与空间优化技巧

处理海量数据时，空间效率是关键。位图（Bitmap）是一种高效的数据结构，特别适用于去重、排序和快速查找等场景。它通过用一个比特位表示一个整数是否存在，将空间占用压缩到极致。

什么是位图

位图本质是一个比特数组，每个比特位代表一个非负整数的状态：0 表示不存在，1 表示存在。例如，要表示数字 5 是否存在，只需将第 5 个比特位置为 1。

相比使用 int 数组或哈希表，位图在存储大量稀疏整数时能节省大量内存。比如表示 1 千万个整数，传统方式可能需要 40MB（每个 int 4 字节），而位图仅需约 1.2MB（10^7 / 8 / 1024 / 1024 ≈ 1.19MB）。

手动实现一个简单的 C++ 位图

下面是一个基础但实用的 Bitmap 类，支持设置、清除、查询和翻转操作：

立即学习“C++免费学习笔记（深入）”；

码上飞

码上飞（CodeFlying）是一款AI自动化开发平台，通过自然语言描述即可自动生成完整应用程序。

430

查看详情

class Bitmap {
private:
    std::vector<uint32_t> bits;
    size_t size;

public:
    explicit Bitmap(size_t n) : size(n) {
        bits.resize((n + 31) / 32, 0);
    }

    void set(size_t i) {
        if (i >= size) return;
        bits[i / 32] |= (1U << (i % 32));
    }

    void clear(size_t i) {
        if (i >= size) return;
        bits[i / 32] &= ~(1U << (i % 32));
    }

    bool get(size_t i) const {
        if (i >= size) return false;
        return (bits[i / 32] & (1U << (i % 32))) != 0;
    }

    void flip(size_t i) {
        if (i >= size) return;
        bits[i / 32] ^= (1U << (i % 32));
    }
};

登录后复制

说明：