如果让你记录“今天哪些用户登录过”，最直接的想法可能是放进一个集合：

logged_in_users = set()
logged_in_users.add(10086)

这样当然能用。但如果用户 ID 范围很大、查询又特别频繁，集合会带来不少额外开销。有没有一种更省空间的办法？

位图，也就是 Bitmap，解决的就是这类问题：用一个 bit 表示一个状态。这个状态通常只有两种结果：有或没有、是或否、出现过或没出现过。

位图到底是什么

先从一个字节说起。

一个字节有 8 个 bit：

0 0 0 0 0 0 0 0

每个 bit 都可以表示一个编号是否存在。比如我们用 bit 记录数字是否出现过：

bit 0 表示数字 0 是否出现
bit 1 表示数字 1 是否出现
bit 2 表示数字 2 是否出现
...
bit 7 表示数字 7 是否出现

如果数字 3 出现过，就把第 3 个 bit 置为 1：

0 0 0 0 1 0 0 0
        ↑
      数字 3

当编号超过 7 时，就放到下一个字节里。比如数字 13：

13 // 8 = 1   -> 放在第 1 个字节
13 % 8  = 5   -> 使用这个字节里的第 5 个 bit

所以位图的核心映射关系只有两行：

字节下标 = 数字 // 8
bit 下标 = 数字 % 8

看到这里，位图就不神秘了。它本质上是一个数组，只不过数组里的每个 bit 都被拿来当成一个小开关。

为什么位图省内存

假设我们要记录 1 亿个用户是否登录过。

如果用普通布尔数组，哪怕一个用户只占 1 个字节，也需要：

100,000,000 字节 ≈ 95 MB

如果用位图，一个用户只占 1 个 bit：

100,000,000 bit ÷ 8 ≈ 12 MB

这还只是和“理想布尔数组”比。实际的 set、dict、对象数组通常还有哈希表、指针、扩容等额外开销，真实内存差距会更大。

这就是位图最适合的地方：状态很简单，但数量很大。

三个核心操作

位图常用操作只有三个：

操作含义
set把某个数字标记为存在
get查询某个数字是否存在
clear清掉某个数字的标记

用位运算表达就是：

set:   bits[index] = bits[index] |  (1 << offset)
get:   bits[index] & (1 << offset) != 0
clear: bits[index] = bits[index] & ~(1 << offset)

如果你不熟悉位运算，可以先这样理解：

  • 1 << offset 是做出一个只有目标位置为 1 的小掩码。
  • | 是把目标 bit 打开。
  • & 是检查目标 bit 是否已经打开。
  • & ~ 是把目标 bit 关掉。

用 Python 写一个最小 Bitmap

下面是一个最小可用的位图。为了让例子简单，它只支持 0 到 max_value 之间的非负整数。

class Bitmap:
    def __init__(self, max_value: int):
        if max_value < 0:
            raise ValueError("max_value must be non-negative")

        self.max_value = max_value
        byte_len = (max_value + 1 + 7) // 8
        self.bits = bytearray(byte_len)

    def _position(self, value: int) -> tuple[int, int]:
        if value < 0 or value > self.max_value:
            raise ValueError("value out of range")

        byte_index = value // 8
        bit_offset = value % 8
        return byte_index, bit_offset

    def add(self, value: int) -> None:
        byte_index, bit_offset = self._position(value)
        self.bits[byte_index] |= 1 << bit_offset

    def contains(self, value: int) -> bool:
        byte_index, bit_offset = self._position(value)
        return (self.bits[byte_index] & (1 << bit_offset)) != 0

    def remove(self, value: int) -> None:
        byte_index, bit_offset = self._position(value)
        self.bits[byte_index] &= ~(1 << bit_offset)

使用方式：

bitmap = Bitmap(100)

bitmap.add(3)
bitmap.add(13)
bitmap.add(88)

print(bitmap.contains(13))  # True
print(bitmap.contains(14))  # False

bitmap.remove(13)
print(bitmap.contains(13))  # False

这个例子里的 bytearray 就是底层存储。每次 add()、contains()、remove() 都先算出目标数字落在哪个字节、哪个 bit，然后对那个 bit 做操作。

一个更贴近日常业务的例子：用户签到

假设一个活动最多有 100 万个用户参与，我们想记录“今天谁签到了”。如果用户 ID 从 0 开始连续增长，就可以这样做：

today_checkin = Bitmap(1_000_000)

def checkin(user_id: int) -> None:
    today_checkin.add(user_id)

def has_checked_in(user_id: int) -> bool:
    return today_checkin.contains(user_id)

查询某个用户是否签到，就是一次数组访问加一次位运算，速度非常快。

如果还要统计“连续两天都签到的人”，位图也很好用。假设昨天和今天各有一个 bitmap：

yesterday = Bitmap(1_000_000)
today = Bitmap(1_000_000)

# 两个位图按字节做 AND，就能得到两天都签到的用户集合
both = bytearray(
    a & b
    for a, b in zip(yesterday.bits, today.bits)
)

这就是位图另一个很强的地方：集合运算很便宜。

  • AND：求交集，比如两天都签到。
  • OR：求并集，比如两天任意一天签到。
  • XOR：求差异，比如两天状态发生变化的人。

这些操作可以按字节、按 64 位整数，甚至借助 CPU 的 SIMD 指令批量执行，比逐个用户判断快得多。

常见使用场景

位图适合很多“编号到状态”的问题。

判断是否出现过

比如判断一个整数是否已经出现：

seen = Bitmap(10_000_000)

def add_number(n: int) -> None:
    seen.add(n)

def exists(n: int) -> bool:
    return seen.contains(n)

如果数字范围可控，位图会比哈希集合更省内存。

用户签到和活跃状态

每天一个 bitmap，用户 ID 对应 bit：

user_id = 10086
bit = 10086

今天登录了，就把对应 bit 置为 1。统计多天活跃、连续活跃、某几天都活跃，都可以用位运算组合。

权限开关

如果一个系统里权限项数量不多，也可以用 bit 表示权限：

bit 0 = 能查看
bit 1 = 能编辑
bit 2 = 能删除
bit 3 = 能发布

一个用户的权限可以压缩成一个整数：

CAN_VIEW = 1 << 0
CAN_EDIT = 1 << 1
CAN_DELETE = 1 << 2

permission = CAN_VIEW | CAN_EDIT

can_edit = (permission & CAN_EDIT) != 0

这种方式常见于权限标记、状态位、功能开关。不过权限系统一旦涉及继承、资源范围、审计和动态策略，就不能只靠一个整数硬扛。

位图不适合什么

位图虽然省内存，但不是所有场景都合适。

编号范围很大但数据很少

如果只存 1000 个用户，但用户 ID 最大可能到 10 亿，直接建一个支持 10 亿范围的位图就不划算：

1,000,000,000 bit ÷ 8 ≈ 119 MB

这时用 set 可能更合适。位图适合的是“范围可控，并且数据比较密集”的场景。

需要记录复杂信息

位图只能表达“是或否”。它不能直接记录：

  • 用户登录了几次。
  • 用户最后一次登录时间。
  • 某个 ID 对应的业务对象。

如果需要这些信息，位图最多只能作为辅助索引，真正的数据还要放在别的结构里。

ID 不是整数或无法映射

位图天然喜欢整数 ID。如果你的 key 是邮箱、手机号、字符串 UUID，就需要先做映射。

这一步要小心：如果只是把字符串 hash 到一个 bit 上，就可能发生冲突。冲突可接受时，可以考虑布隆过滤器；冲突不可接受时，就需要维护一个可靠的 ID 映射。

和布隆过滤器有什么区别

很多人会把位图和布隆过滤器混在一起。它们都用 bit，但目标不一样。

位图是精确的：

数字 13 -> 固定对应第 13 个 bit

只要范围没越界，查询结果就是准确的。

布隆过滤器是概率型的：

一个 key -> 多个 hash -> 多个 bit

它能用更小空间判断“某个元素可能存在，或者一定不存在”。代价是会有误判：它可能说一个元素存在，但实际不存在。

简单说：

结构查询结果适合场景
位图精确整数范围可控，不能接受误判
布隆过滤器可能误判超大规模去重、缓存穿透防护、能接受少量误判

实际使用时的几个小坑

注意边界

如果支持 0 到 max_value，需要的 bit 数是 max_value + 1，不是 max_value。所以字节数最好这样算：

byte_len = (max_value + 1 + 7) // 8

+7 是为了向上取整。比如 9 个 bit 需要 2 个字节，不能只分配 1 个字节。

注意并发写

如果多个线程同时修改同一个字节里的不同 bit，可能会互相覆盖。因为 bits[i] |= mask 看起来是一行，但底层通常是“读出、修改、写回”三个步骤。

高并发场景要使用锁、原子位操作，或者按分片减少竞争。

注意持久化格式

位图很适合持久化，因为它本质就是一段字节数组。但落盘前要想清楚：

  • 最大 ID 范围是多少。
  • bit 顺序是从低位到高位，还是从高位到低位。
  • 是否需要版本号，方便以后扩展。
  • 是否需要压缩，比如 Roaring Bitmap。

尤其是多个语言之间共享位图时，bit 顺序和字节序要写清楚，不然读出来很容易对不上。

总结

位图最核心的思想很简单：用一个 bit 记录一个编号的状态。它适合整数范围可控、状态只有是或否、数据量又很大的场景。

如果你只是记录少量离散数据，用 set 更简单；如果你要记录复杂对象，用数据库或哈希表更自然；但如果你面对的是几千万、几亿个“是否出现过”的状态，位图就是一个非常值得掌握的工具。

判断是否适合用位图，可以记住三个问题：

  1. 这个状态是不是只有是或否？
  2. ID 能不能稳定映射成非负整数？
  3. 最大 ID 范围是不是可控？

三个答案都是“是”，位图通常就值得试一试。