前言
给定一个最多包含40亿个随机排列的32位的顺序整数的顺序文件，找出一个不在文件中的32位整数。（在文件中至少确实一个这样的数-为什么？）。在具有足够内存的情况下，如何解决该问题？如果有几个外部的“临时”文件可用，但是仅有几百字节的内存，又该如何解决该问题？
分析
这仍然是《编程珠玑》中的一个问题。前面我们曾经提到过《位图法》，我们使用位图法解决了这个问题。32位整型最多有4294967296个整数，而很显然40亿个数中必然会至少缺一个。我们同样也可以尝试使用位图法解决该问题，使用536 870 912个字节，约512M内存存储这40亿整数，存在该整数的位置1，最后遍历比特位，输出第一个比特位为0的位置即可。那如果仅借助几个“临时”文件，使用几百字节的内存的情况下该如何处理呢？
能否使用二分搜索呢？这40亿个整数是随机排列的，因此普通的二分搜索不能找到那个不存在的数。但是我们可以基于二分搜索的思想。
一个整数有32位，我们按照每个比特位是0还是1，将要查找的数据范围一分为二。从最高比特位开始：
- 将最高比特位为0的放在一堆，为1的放在另外一堆
- 如果一样多，则随意选择一堆，例如选0，则该位为0
- 如果不一样多，选择少的一堆继续，如1更少，则该位为1
这里需要做一些解释：
- 由于2^32个整数中，每一个比特位是1还是0的个数是相同的。如果在这40亿个整数中，某比特位为1和0的个数是相同的，则说明两边都有不存在的数。因此选择任意一堆即可。
- 如果比特位1的整数比0的整数多，则说明，比特位为0的一堆数中，肯定缺少了一些数。而比特位为1的一堆数中，可能缺少一些数。因此，我们选择少的，也就是比特位为0的那一堆数。
- 每一次选择，都记录选择的是0还是1，最多32次选择后，便可以至少找到一个整数，不存在这40亿数中。
实例说明
由于32位的整型数据量太多，不便说明，我们用一个4比特的数据对上面的思路再做一个说明。4比特最多有16个数。
假设有以下源数据：
对应二进制形式如下(负数在内存中以补码形式存储)：
1.处理第1比特位被分为两部分数据，分别为：
- 比特位为0的
- 比特位为1的
可以看到，第一比特位为1的数为5个，比比特位为0的数要少，因此选择比特位为1的数，继续处理。且第一比特位，获得1.
3.处理第2比特位仍然分为两部分数据，分别为：
- 比特位为0的
- 比特位为1的
可以看到，第一比特位为1的数为3个，比比特位为0的数要多，因此选择比特位为0的数，继续处理。且第二比特位，获得0。
2.处理第3比特位仍然被分为两部分数据，分别为：
- 比特位为0的
- 比特位为1的
明显看到第三比特位为0的数没有，因此选择比特位0，获得0。至此，已经没有必要继续查找了。
我们最终得到了前三个比特位100，因此不存在于这些数中至少有1000,1001，即-8,-7。
代码实现
C语言实现：
代码说明：
- 这里的splitByBit函数根据比特位将数据分为两部分
- closeAllFile用于关闭文件描述符
- findNum函数循环32个比特位，每处理一次得到一个比特位，最终可以得到不存在其中的整数。
利用脚本产生了约2000万个整数：
编译运行：
程序的主要时间花在了读写文件，且占用内存极小。
总结
本文从一个特别的角度用最常见的二分搜索解决了该问题，最多拆分32次，便可从中找到不存在的整数。你有什么更好的思路或优化点，欢迎留言。