能存下“0到40亿是否出现过”，需512MB内存；用std::vector手动位操作更可控；找第一个缺失数可按字节跳过0xFF再查表；内存受限时采用多趟扫描分段处理。
位图能存下40亿个非负整数吗？
不能直接存“40亿个数”，但能存“0到40亿是否出现过”——这是关键区分。40亿 ≈ 2³²，即非负整数中 0 到 2^32 - 1 共 4294967296 个可能值。用 1 bit 表示一个数是否存在，总共需要 2^32 / 8 = 512MB 内存，单机可接受。
注意：题目说“40亿个非负整数”，不是“范围在 0~40亿”，但通常默认数据落在 [0, 2^32) 内；若存在 ≥2³² 的数（如 4294967296），它们不影响位图索引，可直接忽略或单独处理。
怎么用 std::vector 或 std::bitset 构建位图？
std::vector 是空间特化容器，支持随机访问且自动按位存储，适合动态大小；std::bitset 编译期定长、更快，但 42 亿太大无法栈上分配（会爆栈），必须用堆分配或自定义位操作。
实操建议：
- 用
std::vector手动管理位更可控（避免vector迭代器陷阱和性能抖动） - 申请
(1ULL 字节 → 即536870912字节（512MB），用std::vectorbitmap(536870912, 0) - 设数
n对应的位：字节索引n / 8，位偏移n % 8；置位用bitmap[n >> 3] |= (1U - 读取用
(bitmap[n >> 3] >> (n & 7)) & 1
一次遍历后怎么快速找到第一个缺失数？
从 n = 0 开始查，直到遇到未置位的 n —— 但逐个检查最坏要 42 亿次，太慢。实际可优化：
- 先按字节扫描：跳过值为
0xFF的字节（8 个数全存在） - 对非
0xFF字节，用查表法或__builtin_ctz（GCC/Clang）找最低清零位，比如uint8_t b = ~bitmap[i]，再int pos = __builtin_ctz(b)，缺失数就是i * 8 + pos - 若所有字节都是
0xFF，说明0~2^32-1全存在，则缺失的是2^32（即4294967296），但它是第 4294967297 个非负整数，超出原始 40 亿输入规模，属于边界情况
内存不够 512MB 怎么办？
常见限制是机器只有几百 MB 可用内存，或题目隐含“内存受限”。这时不能一次性加载完整位图：
- 分段位图：把
[0, 2^32)拆成 2¹⁶ 段（每段 2¹⁶=65536 个数），每段用 8KB 位图 → 总内存约 8KB × 65536 = 512MB 不变，但可边读边处理，不需全驻留 - 更实用的是“多趟扫描”：第一趟统计每段出现频次，找出频次
- 若连 8KB 都紧张（如嵌入式），改用外部排序 + 归并思路，但 IO 成本高，一般面试/实操中 512MB 是合理假设
真正容易被忽略的是：输入文件可能含重复数，位图天然去重；但若题目要求找“未出现的最小非负整数”，重复不影响结果，无需额外去重逻辑。
C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
