位图本质是用每个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。
这个映射关系不能错，否则所有读写都会偏移 —— 这是初学者最常踩的坑，尤其混淆 / 和 % 的顺序，或误把 bit 偏移当字节偏移。
set、test、reset 三个核心操作怎么写
用 std::vector<uint32_t></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 = 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 & bits, size_t n) {
size_t idx = n / 32;
if (idx >= bits.size()) return;
uint32_t mask = ~(1U
<p>注意点：</p>
<ul>
<li>
<code>set</code> 中用了 <code>1U</code> 而非 <code>1</code>，避免左移时符号扩展问题</li>
<li>
<code>test</code> 必须先检查 <code>idx</code> 边界，否则越界读可能 crash 或返回垃圾值</li>
<li>
<code>reset</code> 的掩码要用按位取反 <code>~</code>，不是 <code>-</code> 或 <code>!</code>
</li>
</ul>
<h3>位图大小怎么预估才不浪费也不溢出</h3>
<p>如果最大要存的数是 <code>N</code>（0 到 N inclusive），那么需要的 bit 数是 <code>N + 1</code>，对应 <code>uint32_t</code> 元素个数是 <code>(N + 1 + 31) / 32</code>（即向上取整）。直接写成 <code>(N + 31) / 32</code> 是错的 —— 当 <code>N=0</code> 时会得 0，但至少需要 1 个 bit。</p>
<p>更安全的写法是：<code>size_t words = (N + 1 + 31) / 32;</code> 或用标准库：<code>std::bit_ceil(N + 1U) / 32</code>（C++20）。</p>
<p>实际中建议多留一点余量，比如预计最大到 10000，就分配 <code>10000 / 32 + 2</code> 个 <code>uint32_t</code>，避免频繁 <code>resize</code> 带来的拷贝开销。</p>
<p>边界对齐、无符号移位、越界防护 —— 这三点漏掉任何一个，位图就会在某个特定 <code>n</code> 值上静默出错，很难 debug。</p></uint32_t></uint32_t>C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
