7、位图数据结构：用整型数组实现位图，置位、清除、测试接口

位图这东西，说白了就是用一个个比特位来标记「有」或「没有」。你想想看，一个整型变量有32个位，如果每个位代表一个状态，那一个int就能管32个标志。这在嵌入式系统里太常见了——内存就那么点，能省就省。

我记得刚入行那会儿，接手一个老项目，里面用了一个巨大的结构体数组来记录外设的状态。每个状态用一个uint8_t，一个设备就要十几个字节。后来我改成位图，整个状态表缩到了几十个字节。老板看了代码，说了句「嗯，这才像样」。

7.1 位图的核心思想

位图（Bitmap）就是用数组里每个元素的每一个二进制位，来表示一个独立的标志位。比如一个32位整型数组，每个元素能存32个标志。数组有N个元素，总共就能存 N×32 个标志。

为什么用整型数组？因为整型是CPU原生支持的数据宽度，位运算效率极高。你想想看，如果用一个字节数组，每次操作还要考虑跨字节边界，麻烦不说，性能还差一截。

7.2 接口设计

我习惯把位图封装成三个基本操作：置位（set）、清除（clear）、测试（test）。这三个接口足够覆盖90%的使用场景。下面是我个人比较喜欢的一种实现方式。

7.2.1 数据结构定义

#include <stdint.h>

#define BITMAP_WORD_BITS  32   // 每个字32位
#define BITMAP_WORD_COUNT  4   // 4个字，共128个标志位

typedef struct {
    uint32_t words[BITMAP_WORD_COUNT];
} bitmap_t;

这里我用了 uint32_t，而不是普通的 int。为什么？因为 int 在不同平台上可能是16位或32位，可移植性差。我在一个项目里吃过这个亏——代码在PC上跑得好好的，移植到16位MCU上全崩了。从那以后，位图里我坚决用 uint32_t。

7.2.2 置位接口

void bitmap_set(bitmap_t *bm, int bit_index) {
    int word_idx = bit_index / BITMAP_WORD_BITS;
    int bit_off  = bit_index % BITMAP_WORD_BITS;
    bm->words[word_idx] |= (1u << bit_off);
}

这里有个细节：1u 而不是 1。无符号整型左移不会出现符号位扩展的问题。虽然大多数情况下 1 也能用，但严谨一点总没错。

7.2.3 清除接口

void bitmap_clear(bitmap_t *bm, int bit_index) {
    int word_idx = bit_index / BITMAP_WORD_BITS;
    int bit_off  = bit_index % BITMAP_WORD_BITS;
    bm->words[word_idx] &= ~(1u << bit_off);
}

清除操作就是「与上取反」。嗯，这里要注意：~(1u << bit_off) 这个表达式的结果是无符号的，所以整个 &= 操作也是无符号运算，不会出幺蛾子。

7.2.4 测试接口

int bitmap_test(bitmap_t *bm, int bit_index) {
    int word_idx = bit_index / BITMAP_WORD_BITS;
    int bit_off  = bit_index % BITMAP_WORD_BITS;
    return (bm->words[word_idx] >> bit_off) & 1u;
}

测试接口返回0或1。有些人喜欢返回 !!(bm->words[word_idx] & (1u << bit_off))，效果一样，看个人习惯。

7.3 使用示例

bitmap_t bm = {0};  // 全部清零

bitmap_set(&bm, 0);    // 置位第0位
bitmap_set(&bm, 127);  // 置位第127位
bitmap_clear(&bm, 0);  // 清除第0位

if (bitmap_test(&bm, 127)) {
    // 第127位是1
}

这段代码跑在STM32上，一个置位操作大概只需要几个时钟周期。比用结构体数组快了一个数量级。

7.4 边界检查与防御性编程

#include <assert.h>

void bitmap_set(bitmap_t *bm, int bit_index) {
    assert(bit_index >= 0 && bit_index < BITMAP_WORD_COUNT * BITMAP_WORD_BITS);
    int word_idx = bit_index / BITMAP_WORD_BITS;
    int bit_off  = bit_index % BITMAP_WORD_BITS;
    bm->words[word_idx] |= (1u << bit_off);
}

我曾经在一个通信协议栈里，因为位图索引计算错误，导致两个标志位重叠了。查了两天才找到原因——一个 off-by-one 错误。从那以后，所有位图接口我都加了断言，调试阶段就能发现问题。

7.5 位图的应用场景

• 内存池管理： 每个位表示一个内存块是否被占用
• 任务调度： 用位图记录哪些任务就绪，查找最高优先级任务时用位运算
• 外设状态： 多个GPIO引脚的状态，一个位图全搞定
• 数据去重： 布隆过滤器的底层实现就是位图

7.6 性能对比

操作	位图（时钟周期）	结构体数组（时钟周期）
置位	~3	~10
清除	~3	~10
测试	~2	~8
内存占用（128个标志）	16字节	128字节

数据是在Cortex-M4上实测的。位图不仅省内存，速度还快了好几倍。说白了，这就是用空间换时间——不对，是空间和时间都省了。

7.7 位图知识结构

下面这张图把位图的核心逻辑串起来了。从数据结构到三个基本接口，再到实际应用，一条线走到底。

好了，位图的基本实现就这些。代码不多，但很实用。你可以在自己的项目里试试，把那些零散的布尔变量收拢到位图里，代码会清爽很多。