c++怎么实现一个简单的位图（Bitmap）_c++位图结构与应用示例-C++-PHP中文网

c++怎么实现一个简单的位图（Bitmap）_c++位图结构与应用示例

穿越時空

发布： 2025-11-01 08:46:02

原创

950人浏览过

位图用比特表示整数存在状态，节省内存。通过vector<char>或bitset实现，支持set、clear、get操作，适用于去重排序小整数，如输出2 3 5 7 8；std::bitset适合固定大小场景，手动实现更灵活，广泛用于系统级设计。

c++怎么实现一个简单的位图（bitmap）_c++位图结构与应用示例

在C++中，位图（Bitmap）是一种高效的数据结构，用于表示一组布尔状态，通常用来标记某个整数是否出现过。它的核心思想是用一个比特（bit）来表示一个元素的存在与否，从而极大节省内存空间。

位图的基本原理

假设我们要处理的整数范围是 0 到 N-1，那么可以用 N 个比特来表示这些整数的状态：0 表示未出现，1 表示已出现。由于一个字节有8位，我们可以使用 unsigned char 或 std::vector<bool> 来存储这些比特。

更高效的做法是使用 std::vector<char> 或 std::bitset，通过位操作直接访问特定位置的比特。

手动实现简单的位图类

下面是一个基于 vector<char> 的简单位图实现：

#include <iostream>
#include <vector>

class Bitmap {
private:
    std::vector<char> bits;
    int size;

public:
    // 构造函数，指定最大数值范围
    Bitmap(int n) : size(n) {
        bits.resize((n + 7) / 8, 0);  // 每个 char 8 bit，向上取整
    }

    // 设置某一位为 1
    void set(int i) {
        if (i < 0 || i >= size) return;
        int byteIndex = i / 8;
        int bitIndex = i % 8;
        bits[byteIndex] |= (1 << bitIndex);
    }

    // 清除某一位为 0
    void clear(int i) {
        if (i < 0 || i >= size) return;
        int byteIndex = i / 8;
        int bitIndex = i % 8;
        bits[byteIndex] &= ~(1 << bitIndex);
    }

    // 检查某一位是否为 1
    bool get(int i) {
        if (i < 0 || i >= size) return false;
        int byteIndex = i / 8;
        int bitIndex = i % 8;
        return (bits[byteIndex] & (1 << bitIndex)) != 0;
    }
};

登录后复制

使用示例：去重与排序小整数

位图常用于对非负整数进行快速去重和排序。比如我们有一组数据，想输出不重复且有序的结果：

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

凡科AI抠图

简单好用的在线抠图工具

查看详情

int main() {
    Bitmap bm(100);  // 支持 0~99

    int nums[] = {5, 2, 7, 5, 3, 2, 8, 7};
    int n = sizeof(nums) / sizeof(nums[0]);

    // 插入所有数字（自动去重）
    for (int i = 0; i < n; ++i) {
        bm.set(nums[i]);
    }

    // 按顺序输出存在的数字
    std::cout << "Unique sorted numbers: ";
    for (int i = 0; i < 100; ++i) {
        if (bm.get(i)) {
            std::cout << i << " ";
        }
    }
    std::cout << std::endl;

    return 0;
}

登录后复制

输出结果：

Unique sorted numbers: 2 3 5 7 8

标准库替代方案：std::bitset

如果大小在编译期已知，可以直接使用 std::bitset，它更安全且接口简洁：

#include <bitset>
#include <iostream>

int main() {
    std::bitset<100> bs;  // 固定大小为100

    bs.set(5);
    bs.set(2);
    bs.set(7);
    bs.set(5);  // 重复设置无影响

    for (int i = 0; i < 100; ++i) {
        if (bs.test(i)) {
            std::cout << i << " ";
        }
    }
    std::cout << std::endl;

    return 0;
}

登录后复制

基本上就这些。自己实现的 Bitmap 更灵活，可动态扩展；而 std::bitset 更适合固定场景，写起来更简单。实际应用中，位图广泛用于布隆过滤器、内存页管理、文件系统索引等底层系统设计中。注意它只适用于整数且范围不太大的情况，超出后要考虑 Roaring Bitmap 等优化结构。

以上就是c++++怎么实现一个简单的位图（Bitmap）_c++位图结构与应用示例的详细内容，更多请关注php中文网其它相关文章！