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

新闻中心 NEWS CENTER

您当前位置：首页 > 新闻中心 > 网络学院

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

2025-11-16

浏览次数：次

返回列表

位图通过位操作高效管理布尔状态，使用std::vector按位存储，支持set、reset、get操作，适用于去重、排序等场景，空间时间效率优于集合容器。

c++如何实现一个简单的位图(bitmap)_c++数据结构与位图实现

位图（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 不存在

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

Zyro AI Background Remover

Zyro推出的AI图片背景移除工具

145 查看详情 Zyro AI Background Remover

关键位操作

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

确定所在整数位置：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 <iostream>
#include <vector>

class Bitmap {
private:
    std::vector<unsigned int> 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）等。不复杂但容易忽略边界检查和位运算细节。

以上就是C++如何实现一个简单的位图(Bitmap)_C++数据结构与位图实现的详细内容，更多请关注其它相关文章！

# 是一种 # 旅游线路推广和营销方案 # 乐清营销推广平台 # 低价网站建设的优缺点 # 什么是新媒体seo # 关于网站建设图片 # 合肥抖音推广营销好做吗 # 建设网站价格app手机 # 电销营销网站建设 # 丹东建设网站企业 # 全国大学优秀网站建设 # 相关文章 # 还可以 # ai # 边缘 # 是否存在 # 整型 # 适用于 # 如何实现 # 游戏开发 # 数据结构 # red # stream # ios # c++