A1 · 位图找缺失整数
来源：《编程珠玑》开篇问题 A（内存足够时）
题意
给定一个最多包含 40 亿 个随机排列的 32 位整数 的顺序文件，找出一个不在文件中的 32 位整数。
- 至少缺失一个——为什么？因为 (2^{32} = 4,294,967,296 > 40) 亿。
- 本篇假设：内存足够（大约能放下 512MB 级结构）。
思路
开一张覆盖全体 32 位整数的位图：
- 下标 = 数值本身（不是文件里的位置）
- 值 0/1 = 有没有出现过
扫一遍文件打标，再扫一遍位图找第一个为 0 的下标。
| 含义 | |
|---|---|
bitmap[2] = 1 | 数字 2 出现过 |
bitmap[5] = 0 | 数字 5 没出现过 → 可作答案 |
重复数字无妨：同一位写两次仍是 1。
原理图
交互演示
Java 伪代码
// 找任意一个缺失的 32 位无符号整数（内存足够）
int findMissingBitmap(IntStream file) {
// 2^32 bit ≈ 512MB；也可用 BitSet / byte[] 按位打包
BitSet bitmap = new BitSet(1 << 30); // 示意：真实需覆盖满 2^32
// 更直白的示意：
// byte[] bits = new byte[1 << 29]; // 2^32 / 8
for (int x : file) {
// 下标 = 数值（按无符号理解时注意 >>>）
bitmap.set(Integer.toUnsignedLong(x) /* 映射到 bit 下标 */);
// 等价：bits[x >>> 3] |= (1 << (x & 7));
}
for (long i = 0; i < (1L << 32); i++) {
if (!bitmap.get(/* i */)) {
return (int) i; // 找到一个缺失即可
}
}
throw new IllegalStateException("理论不应发生");
}更贴近「纯数组」的写法：
void mark(byte[] bits, int x) {
bits[x >>> 3] |= (1 << (x & 7));
}
boolean test(byte[] bits, int x) {
return (bits[x >>> 3] & (1 << (x & 7))) != 0;
}复杂度
| 时间 | (O(n + U))，(U=2^{32})；实践上主要是扫一遍文件 |
| 空间 | 固定约 512MB（(2^{32}) bit） |
相对哈希表：本题值域稠密，位图更省、更快。哈希表优势在稀疏 / 值域巨大时。