第2章位图数据结构基础

位图数据结构基础

各位同学，今天咱们来聊聊位图。说实话，我在做RTOS内核开发的头两年，一直觉得位图就是个花架子。直到有一次，我在一个资源极度受限的MCU上做任务调度，内存只剩几百字节，传统的链表调度器根本塞不下。那时候我才真正体会到——位图这东西，简直是嵌入式开发的救命稻草。

位图，说白了就是用一个个二进制位来表示状态。每个位只有0或1两种取值，0代表「没有」，1代表「有」。你想想看，一个32位的整型变量，就能表示32个不同的状态。这在嵌入式系统里意味着什么？意味着你用4个字节，就能管理32个任务的就绪状态。

我习惯把位图想象成一个停车场的车位灯。每个车位对应一个位，灯亮表示有车（1），灯灭表示空位（0）。你要找空车位，扫一眼就知道。位图在RTOS里干的事，本质上就是这件事——快速找到哪个任务准备好了。

核心概念：位图 = 一组二进制位的集合，每个位代表一个独立的状态或标志。

要玩转位图，你得先搞定位运算。这部分其实不难，但容易搞混。我刚开始学的时候，经常把与和或搞反，后来写了个小口诀才记住。

两个位都是1，结果才是1。说白了就是「都满足才行」。我在项目中常用它来清除特定位——你想把某一位清零，就构造一个该位为0、其他位为1的掩码，然后做与运算。

// 清除第3位（从0开始计数）
uint32_t flags = 0b11111111;
uint32_t mask = ~(1 << 3);  // 0b11110111
flags = flags & mask;       // 结果：0b11110111

只要有一个是1，结果就是1。这用来置位特别方便。你想把某一位设为1，构造一个该位为1的掩码，做或运算就行。

// 设置第5位
uint32_t flags = 0b00000000;
uint32_t mask = 1 << 5;     // 0b00100000
flags = flags | mask;       // 结果：0b00100000

两个位不同，结果为1；相同则为0。这个操作很有意思，它相当于「翻转」。同一个位异或两次，就回到原值。我在做状态机切换时经常用它——比如LED闪烁控制，每次异或1就能切换亮灭。

// 翻转第2位
uint32_t flags = 0b00000100;
flags = flags ^ (1 << 2);   // 结果：0b00000000
flags = flags ^ (1 << 2);   // 结果：0b00000100（又回来了）

0变1，1变0。这个操作通常配合其他运算使用。比如前面清除位时，就是先左移构造一个1，然后取反得到掩码。

注意：取反操作是对整个数据类型的所有位取反。如果你只想要低8位取反，记得用掩码截断，否则高位也会被翻转。我曾经在这个坑里栽过跟头——调试了整整一个下午才发现是取反把高位也改了。

左移就是往高位移动，低位补0。右移分两种：逻辑右移高位补0，算术右移高位补符号位。在嵌入式里，我们几乎只用逻辑右移（无符号数）。

// 左移：相当于乘以2的n次方
uint32_t a = 1 << 3;   // 结果：8

// 右移：相当于除以2的n次方
uint32_t b = 16 >> 2;  // 结果：4

为什么RTOS内核偏爱位图？我总结了三个核心优势，都是我在实际项目中反复验证过的。

内存效率这块，我举个例子你就明白了。假设你要管理64个任务的就绪状态。用传统数组，至少需要64个字节（每个任务一个字节）。用位图呢？8个字节就够了。在只有2KB RAM的单片机上，这差距可不是一星半点。

运算速度方面，位运算都是CPU的单周期指令。你想想看，判断一个任务是否就绪，位图只需要一条AND指令。换成链表遍历？那得循环几十次。我在一个Cortex-M0的项目里做过对比，位图调度比链表调度快了将近20倍。

查找效率这块最有意思。大多数ARM Cortex-M系列芯片都内置了CLZ（Count Leading Zeros）指令。配合位图，你可以在3个时钟周期内找到最高优先级的就绪任务。这个特性，是位图调度算法能成为RTOS主流方案的根本原因。

个人经验：我建议你在设计RTOS调度器时，优先考虑位图方案。除非你的任务数超过256个，否则位图在各方面都优于其他数据结构。我曾经在一个项目里硬要用链表实现优先级调度，结果代码写出来又臭又长，性能还差。后来改成位图，代码量直接砍掉一半。

嗯，这里要补充一点。位图也不是万能的。如果你的任务优先级是动态变化的，或者需要频繁插入删除，位图维护起来会稍微麻烦一些。但对于固定优先级的RTOS调度场景，位图就是最优解，没有之一。

下一章，我会带你手写一个位图调度器的核心代码。到时候你会发现，真正写起来比想象中简单得多。