位图本质是用每个bit表示一个状态，非图像；如记录0~999整数状态，位图仅需125字节，为bool数组的1/8；通过整数数组加位运算访问，n对应字节索引为n>>3，bit偏移为n&7。
位图的本质就是用每个 bit 表示一个状态
位图（Bitmap）不是图像，而是用一个二进制位（bit）代表某个整数是否存在、是否被标记、是否被占用。比如想记录 0~999 这 1000 个整数的出现状态，用 bool 数组要占 1000 字节；而用位图，只需要 ⌈1000/8⌉ = 125 字节——空间压缩到 1/8。
关键在于：不直接操作 bit，而是通过整数数组 + 位运算间接访问。C++ 没有原生 bit 数组类型，所以得用 unsigned char 或 uint32_t 数组模拟。
如何计算 bit 所在字节和偏移位置
给定整数 n（从 0 开始），它对应的 bit 在数组中的位置由两部分决定：
- 所在字节索引：
n / 8（或n >> 3） - 在该字节内的 bit 偏移：
n % 8（或n & 7）
例如 n = 13：字节索引是 1（因为 13÷8=1 余 5），bit 偏移是 5，对应掩码是 1 ，即 <code>0x20。
立即学习“C++免费学习笔记（深入）”；
这个映射关系不能错，否则所有读写都会偏移 —— 这是初学者最常踩的坑，尤其混淆 / 和 % 的顺序，或误把 bit 偏移当字节偏移。
set、test、reset 三个核心操作怎么写
用 std::vector<uint32_t> 更省空间（比 unsigned char 少些内存管理开销），但要注意：每个 uint32_t 管 32 个 bit，所以索引公式要换成 n / 32 和 n & 31。
以下是紧凑实现（假设用 uint32_t 数组）：
void set(std::vector<uint32_t>& bits, size_t n) {
size_t idx = n / 32;
uint32_t mask = 1U << (n & 31);
if (idx >= bits.size()) bits.resize(idx + 1, 0);
bits[idx] |= mask;
}
bool test(const std::vector<uint32_t>& bits, size_t n) {
size_t idx = n / 32;
if (idx >= bits.size()) return false;
uint32_t mask = 1U << (n & 31);
return (bits[idx] & mask) != 0;
}
void reset(std::vector<uint32_t>& bits, size_t n) {
size_t idx = n / 32;
if (idx >= bits.size()) return;
uint32_t mask = ~(1U << (n & 31));
bits[idx] &= mask;
}
注意点：
-
set中用了1U而非1，避免左移时符号扩展问题 -
test必须先检查idx边界，否则越界读可能 crash 或返回垃圾值 -
reset的掩码要用按位取反~，不是-或!
位图大小怎么预估才不浪费也不溢出
如果最大要存的数是 N（0 到 N inclusive），那么需要的 bit 数是 N + 1，对应 uint32_t 元素个数是 (N + 1 + 31) / 32（即向上取整）。直接写成 (N + 31) / 32 是错的 —— 当 N=0 时会得 0，但至少需要 1 个 bit。
更安全的写法是：size_t words = (N + 1 + 31) / 32; 或用标准库：std::bit_ceil(N + 1U) / 32（C++20）。
实际中建议多留一点余量，比如预计最大到 10000，就分配 10000 / 32 + 2 个 uint32_t，避免频繁 resize 带来的拷贝开销。
边界对齐、无符号移位、越界防护 —— 这三点漏掉任何一个，位图就会在某个特定 n 值上静默出错，很难 debug。
