c++怎么实现一个位图(Bitmap)数据结构_c++位运算与空间优化实现

技术教程
2025-11-17 16:58:41

位图用位存储布尔状态，C++中通过位运算高效实现，以字节数组为底层存储，每bit代表一个整数是否存在，支持set、clear、test操作，节省内存至N/8字节。

c++怎么实现一个位图(bitmap)数据结构_c++位运算与空间优化实现

位图（Bitmap）是一种用单个位来存储信息的数据结构，适合处理大量布尔状态的场景，比如去重、排序、布隆过滤器等。C++中通过位运算和空间优化可以高效实现一个轻量级的 Bitmap。

基本原理与设计思路

一个 bit 可以表示 0 或 1 状态，如果我们想记录 N 个整数是否存在，传统数组需要 N 字节，而位图只需 N/8 字节（向下取整并加一），大幅节省内存。

核心思想是：用一个字节数组（或整型数组）作为底层存储，每个 bit 代表一个整数是否出现过。例如第 i 个 bit 为 1 表示整数 i 存在。

关键操作：

set(i)：将第 i 位置 1
clear(i)：将第 i 位置 0
test(i)：查询第 i 位是否为 1

位运算实现细节

使用位运算对指定位置进行操作。假设我们有一个 unsigned char 数组，要操作第 i 位：

确定该位所在的字节下标：i / 8 或 i >> 3
确定在字节内的偏移量：i % 8 或 i & 7
设置某一位：使用按位或 |= (1
清除某一位：使用按位与 &= ~(1
测试某一位：使用按位与判断结果是否非零

代码示例：

Veed AI Voice Generator

Veed推出的AI语音生成器

119 查看详情 Veed AI Voice Generator

class Bitmap {
private:
    std::vector<unsigned char> data;
    size_t n_bits;
<p>public:
explicit Bitmap(size_t bits) : n_bits(bits) {
data.resize((bits + 7) / 8, 0); // 向上取整
}</p><pre class="brush:php;toolbar:false;">void set(size_t i) {
    if (i >= n_bits) return;
    size_t byte_idx = i >> 3;
    size_t offset   = i & 7;
    data[byte_idx] |= (1U << offset);
}

void clear(size_t i) {
    if (i >= n_bits) return;
    size_t byte_idx = i >> 3;
    size_t offset   = i & 7;
    data[byte_idx] &= ~(1U << offset);
}

bool test(size_t i) const {
    if (i >= n_bits) return false;
    size_t byte_idx = i >> 3;
    size_t offset   = i & 7;
    return (data[byte_idx] & (1U << offset)) != 0;
}

};

空间优化技巧

为了进一步提升性能和减少内存占用，可以考虑以下几点：

使用 uint32_t 或 uint64_t 替代 unsigned char 数组，减少边界检查次数，提高缓存命中率
采用模板参数指定元素类型，实现通用性
预分配足够空间避免频繁扩容
批量操作时可用“平行位”技术或内置函数如 __builtin_popcount 统计 1 的个数

进阶版使用 uint32_t 数组的例子：

template<typename Block = uint32_t>
class FastBitmap {
    static constexpr int BITS_PER_BLOCK = sizeof(Block) * 8;
    std::vector<Block> data;
    size_t n_bits;
<p>public:
explicit FastBitmap(size_t bits) : n_bits(bits) {
data.resize((bits + BITS_PER_BLOCK - 1) / BITS_PER_BLOCK, 0);
}</p><pre class="brush:php;toolbar:false;">void set(size_t i) {
    if (i >= n_bits) return;
    size_t block = i / BITS_PER_BLOCK;
    size_t offset = i % BITS_PER_BLOCK;
    data[block] |= (Block(1) << offset);
}

bool test(size_t i) const {
    if (i >= n_bits) return false;
    size_t block = i / BITS_PER_BLOCK;
    size_t offset = i % BITS_PER_BLOCK;
    return (data[block] & (Block(1) << offset)) != 0;
}

void clear(size_t i) {
    if (i >= n_bits) return;
    size_t block = i / BITS_PER_BLOCK;
    size_t offset = i % BITS_PER_BLOCK;
    data[block] &= ~(Block(1) << offset);
}