BitMap本质是一段连续内存，每个bit表示一个非负整数是否存在；用bytearray或array.array('B')实现，索引n对应字节偏移n>>3、位偏移n&7。
BitMap 本质是啥？别被名字唬住
BitMap 就是一段连续的内存，每个 bit 代表一个整数是否存在。比如第 i 位为 1，表示整数 i 在集合中；为 0 表示不存在。它不是 Python 内置类型，得自己用 bytearray 或 array.array('B') 搭建底层存储，再靠位运算操作。
关键点：索引必须是非负整数，且最大值不能超过 len(bitmap) * 8 - 1。越界访问不会报错，但结果不可预测——这是最常踩的坑。
怎么算 byte 和 bit 的位置？别手算出错
给定整数 n，它在 BitMap 中的位置由两部分决定：n // 8 是字节偏移，n % 8 是该字节内的 bit 偏移（从右往左，0~7）。实际用的时候推荐直接写成 n >> 3 和 n & 7，更快更安全。
-
set_bit(n)：bitmap[n >> 3] |= (1 -
get_bit(n)：(bitmap[n >> 3] >> (n & 7)) & 1 -
clear_bit(n)：bitmap[n >> 3] &= ~(1
注意：Python 的 int 是任意精度，但 1 这种在旧版 CPython 下可能触发警告（尤其用 <code>array.array 时），建议统一用 bytearray。
立即学习“Python免费学习笔记（深入）”；
为什么不用 set？什么时候该上 BitMap？
当你要判断「1 亿以内整数是否存在」，用 set 占约 800MB 内存；同样范围的 BitMap 只要 ~12.5MB。但代价是：只支持非负整数、不支持动态扩容、无法遍历元素（除非全扫描）。
典型适用场景：
- 去重后统计某批日志里的用户 ID（ID 范围已知且集中）
- 布隆过滤器底层存储（配合哈希函数）
- 内存受限服务里做快速存在性校验（如限流白名单）
常见误用：拿 BitMap 存负数或超大稀疏 ID（比如只有 1 和 999999999），这时反而浪费空间、降低 cache 局部性。
Python 实现要注意的三个细节
一是初始化大小别写死。比如要覆盖 [0, N)，需申请 (N + 7) // 8 字节，不是 N // 8；二是 bytearray 默认填 0，省去清零步骤；三是多线程下没加锁，set_bit 不是原子操作——两个线程同时设同一个 bit，可能丢一次写入。
简单可靠写法：
size_bytes = (max_n + 7) // 8 bitmap = bytearray(size_bytes) <p>def set_bit(n): if n < 0 or n >= max_n: return bitmap[n >> 3] |= (1 << (n & 7))</p><p>def has_bit(n): if n < 0 or n >= max_n: return False return bool(bitmap[n >> 3] & (1 << (n & 7)))
边界检查不能省，Python 不会帮你拦住 n = -1 或 n = len(bitmap)*8 这种越界访问——它会静默 wrap around，结果完全不对。
