某数组A[1..n]含有所有从0到n的整数，但其中有一个整数不在数组中。通过利用一个辅助数组B[0..n]来记录A中出现的整数，很容易在O(n)时间内找出所缺的整数。但在这个问题中，我们却不能有一个单一操作来访问A中的一个完整整数，因为A中的元素是以二进制表示的。我们所能用的唯一操作就是“取A[i]的第j位”，这个操作所花的时间为常数。
证明：如果仅用此操作，仍能在O(n)时间内找出所缺的整数。

我可以在O(nlgn)的时间内找出来，但实在想不出O(n)的算法。

谢谢大家11