位图Bitmap

用单个比特表示一个位置的状态或集合成员资格。

核心约束: 比特与被跟踪对象或区域存在确定映射。
适用问题: 稠密整数集合、CPU 集合、脏块跟踪。
边界与取舍: 稀疏大值域可能浪费空间；粒度影响精度。

每位表示一个状态；先定位机器字，再用位掩码访问对应位。

常见操作#

U 为值域大小，w 为机器字位数；这是未压缩位图。

操作	时间复杂度	条件与说明
测试 / 设置 / 清除一个位	$O(1)$	固定宽度索引可直接定位字和位。
并集 / 交集 / 差集	$O\left(\frac{U}{w}\right)$	逐机器字进行位运算，尾部不足一字需掩码处理。
计数 / 扫描全值域	$O\left(\frac{U}{w}\right)$	假定单字 popcount 或位扫描是常数成本；输出所有成员还需 $O(k)$ 。
初始化 / 清空	$O\left(\frac{U}{w}\right)$	写零所有存储字；惰性清理是另一种实现。

时间与空间#

时间复杂度: 单点 $O(1)$ ；集合运算 $O\left(\frac{U}{w}\right)$
存储空间: $O(U)$ 位

按值域分配，稀疏大值域可能浪费空间；Roaring 等压缩位图需独立分析。

工程中的应用#

3 个案例 · 附源码

QEMU·块设备增量备份v9.2.0

用位图定位增量备份范围

QEMU dirty bitmap 为磁盘区间记录是否被写入，使增量备份能够只复制发生变化的范围。

附源码片段 · 存储与数据放置

libvirt·QEMU 驱动 / CPU 亲和性v10.10.0

把可运行 CPU 集合传递给虚拟机线程

libvirt 将 vCPU 允许使用的宿主 CPU 集合表示为位图，并转换为运行时亲和性配置。

附源码片段 · 调度与资源分配

Linux Kernel·timer_list 普通定时器v6.12

让大量普通超时按时间槽批量到期

Linux 普通定时器把较近超时放进细粒度槽，远期超时放进粗粒度槽，使用位图寻找待处理槽。v6.12 的这套时间轮不再逐层级联迁移。

时间轮侵入式容器位图

附源码片段 · 调度与资源分配

基础原理参考资料

Linux 6.12 · Bitmap operations位图 API、集合运算和尾位处理。

Java 21 · BitSet按位读写、逻辑运算与设置位遍历。