c++怎么实现一个位图(bitmap)_c++位操作实现高效数据标记-C++-PHP中文网

c++怎么实现一个位图(bitmap)_c++位操作实现高效数据标记

穿越時空

发布： 2025-10-24 22:34:02

原创

724人浏览过

位图通过位操作用少量内存高效标记大量整数状态，核心是使用std::vector<unsigned int>按位存储，每个bit表示一个整数的存在与否，支持快速的set、clear、get操作，并可扩展优化如64位块、popcount统计等，适用于去重、排序、资源管理等场景。

c++怎么实现一个位图(bitmap)_c++位操作实现高效数据标记

在C++中实现一个位图（Bitmap），核心是用少量内存高效标记大量整数状态，比如记录某个整数是否出现过、某个资源是否被占用等。通过位操作直接管理二进制位，可以将空间消耗降低到传统布尔数组的1/8甚至更少。

基本原理与设计思路

位图本质是一个大数组，每个比特（bit）代表一个数据项的状态：0表示未标记，1表示已标记。假设要管理从0到N-1的整数，就需要至少N个bit的空间。

例如，管理0~31的整数，只需要一个unsigned int（通常32位）即可；管理0~9999，则需要约10000 / 32 ≈ 313个unsigned int。

关键点：

使用std::vector<unsigned int>或裸指针管理位存储块
通过位运算实现单个bit的设置、清除、查询
支持快速清零、填充、遍历等操作

位操作基础：如何定位和修改某一位

给定一个整数index，找出它在哪个整型单元中，以及在该单元中的第几位。

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

所在块索引： index / 32 或等价于 index >> 5
位偏移： index % 32 或等价于 index & 0x1F
设置位： bits[block] |= (1U << offset)
清除位： bits[block] &= ~(1U << offset)
查询位： (bits[block] >> offset) & 1

这些位运算非常高效，编译器通常会优化成CPU原生指令。

一键职达

AI全自动批量代投简历软件，自动浏览招聘网站从海量职位中用AI匹配职位并完成投递的全自动操作，真正实现'一键职达'的便捷体验。

查看详情

简易位图类实现示例

下面是一个轻量级、可复用的Bitmap实现：

class Bitmap {
private:
    std::vector<unsigned int> data;
    int size; // 总共管理多少位

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

    void set(int index) {
        if (index < 0 || index >= size) return;
        int block = index >> 5;
        int offset = index & 0x1F;
        data[block] |= (1U << offset);
    }

    void clear(int index) {
        if (index < 0 || index >= size) return;
        int block = index >> 5;
        int offset = index & 0x1F;
        data[block] &= ~(1U << offset);
    }

    bool get(int index) const {
        if (index < 0 || index >= size) return false;
        int block = index >> 5;
        int offset = index & 0x1F;
        return (data[block] >> offset) & 1;
    }

    void reset() {
        std::fill(data.begin(), data.end(), 0);
    }
};

登录后复制

这个实现简洁且高效，适合嵌入式、算法题或高性能场景。