如果我们假设数字的范围总是 2^n（2 的偶数次幂），那么异或将起作用（如另一张海报所示）。至于为什么，让我们证明一下：
理论
给定任何基于 0 的整数范围，2^n其中包含缺少一个元素的元素，您可以通过简单地将已知值异或在一起以产生缺失的数字来找到缺失的元素。
证据
让我们看看 n = 2。对于 n=2，我们可以表示 4 个唯一整数：0、1、2、3。它们的位模式为：
- 0 - 00
- 1 - 01
- 2 - 10
- 3 - 11
现在，如果我们看一下，每个位都被设置了两次。因此，由于它被设置了偶数次，并且数字的异或将产生 0。如果缺少单个数字，异或将产生一个数字，当与缺少的数字异或时将导致0. 因此，缺失的数和得到的异或数完全相同。如果我们删除 2，结果 xor 将是10（或 2）。
现在，让我们看一下n+1。我们称每个位被设置的次数为n，x每个位被设置的次数为n+1 y。的值y将等于，y = x * 2因为存在位设置为 0 的x元素和位设置为 1 的元素。并且由于将始终为偶数，因此每个位将始终设置偶数次。n+1xn+12xn+1
因此，由于n=2有效，并且n+1有效，xor 方法将适用于 的所有值n>=2。
基于 0 的范围的算法
这很简单。它使用 2*n 位内存，因此对于任何 <= 32 的范围，2 个 32 位整数都可以工作（忽略文件描述符消耗的任何内存）。它只对文件进行一次传递。
long supplied = 0;
long result = 0;
while (supplied = read_int_from_file()) {
result = result ^ supplied;
}
return result;
基于任意范围的算法
该算法适用于任何起始数字到任何结束数字的范围，只要总范围等于 2^n ...这基本上将范围重新设置为最小值为 0。但它确实需要 2 次通过通过文件（第一个获取最小值，第二个计算丢失的 int）。
long supplied = 0;
long result = 0;
long offset = INT_MAX;
while (supplied = read_int_from_file()) {
if (supplied < offset) {
offset = supplied;
}
}
reset_file_pointer();
while (supplied = read_int_from_file()) {
result = result ^ (supplied - offset);
}
return result + offset;
任意范围
我们可以将此修改后的方法应用于一组任意范围，因为所有范围都将至少跨越一次 2^n 的幂。这仅在缺少一个位时才有效。它需要 2 遍未排序的文件，但每次都会找到单个丢失的数字：
long supplied = 0;
long result = 0;
long offset = INT_MAX;
long n = 0;
double temp;
while (supplied = read_int_from_file()) {
if (supplied < offset) {
offset = supplied;
}
}
reset_file_pointer();
while (supplied = read_int_from_file()) {
n++;
result = result ^ (supplied - offset);
}
// We need to increment n one value so that we take care of the missing
// int value
n++
while (n == 1 || 0 != (n & (n - 1))) {
result = result ^ (n++);
}
return result + offset;
基本上，将范围重新设置为 0 左右。然后，它在计算异或时计算要附加的未排序值的数量。然后，它将未排序值的计数加 1 以处理缺失值（计算缺失值）。然后，继续对 n 值进行异或运算，每次递增 1，直到 n 是 2 的幂。然后将结果重新基于原始基数。完毕。
这是我在 PHP 中测试的算法（使用数组而不是文件，但概念相同）：
function find($array) {
$offset = min($array);
$n = 0;
$result = 0;
foreach ($array as $value) {
$result = $result ^ ($value - $offset);
$n++;
}
$n++; // This takes care of the missing value
while ($n == 1 || 0 != ($n & ($n - 1))) {
$result = $result ^ ($n++);
}
return $result + $offset;
}
输入一个具有任何值范围的数组（我测试过包括负数），其中一个在该范围内丢失，它每次都找到正确的值。
另一种方法
既然我们可以使用外部排序，为什么不只检查间隙呢？如果我们假设文件在运行此算法之前已排序：
long supplied = 0;
long last = read_int_from_file();
while (supplied = read_int_from_file()) {
if (supplied != last + 1) {
return last + 1;
}
last = supplied;
}
// The range is contiguous, so what do we do here? Let's return last + 1:
return last + 1;