我得到了这个关于硬件的问题，但我不知道该怎么做：
数组 A[1...n] 包含从 0 到 n 的所有整数，除了一个。数组未排序。
在这个问题中，我们不能通过单个操作访问 A 中的整个整数。
A 的元素以二进制表示，我们可以用来访问它们的唯一操作是“获取 A[i] 的第 j 位”，这需要恒定的时间。
我必须在 O(n) 时间内找到丢失的整数。
正常执行此操作所需的时间是 O(NlgN) （在 N 数组上运行，并获取所有作为 N - lgn 位函数的位）。
如果不阅读所有位，我怎么能做到这一点？
现在让我们假设对于某些 k，n 是 2^k - 1。
让我们再看一个 k = 3 的例子。
000
001
010
011
100
101
110
111
你会注意到，当有一个完整的集合时，就像上面显示的那样，每一列（每个数字的位置）都有相同数量的 1 和 0。当然，为方便起见，我们将其显示为已排序，但实际上，我并不是说它是排序的。
我们来看看下面的列表
000
001
010
011
100
110
111
我们查看所有元素的第一位（ O(n) ）并找出哪个计数小于另一个。
我们看到，对于第一位，有一个数字，其最高有效位中的 1 缺失。这意味着我们知道我们的数字在其最高有效位中有一个。
基本上，我们分成两组，一组最高有效位为 1，另一组最高有效位为 0。较小的一组向我们展示了缺失数字的位。
我们在较小的分区上做同样的事情。
Since it is O(n) + O(n/2) + O (n/4) ... it is basically O (2n) which is O (n).
EDIT
For the general case, refer to the following document, bottom of page 1.
Basically, it involves making use of the fact that when n is not a power of two, you can take into account the fact that given n, you know exactly how many should fall under the bit=1 partition and the bit=0 partition if this was a complete set.