位操作一题

An array A[1... n] contains all the integers from 0 to n except for one number which is missing. In this problem, we cannot access an entire integer in A with a single operation. The elements of A are represented in binary, and the only operation we can use to access them is “fetch the jth bit of A[i]”, which takes constant time. Write code to find the missing integer. Can you do it in O(n) time?

 

首先我们将0到n的所有数字的二进制表达列出来。那么我们可以发现最低位的，大概是这样的情况：count(0)>=count(1)。
如果我们从中移除了一个数字，会怎么样呢？

如果移除的数最低位为0，那么count(1)>=count(0)；如果移除的是1，那么count(0)>count(1)。如果n次访问每个数的最低位，那么用以上的准则我们就能判断出没有进入数组的那个数字的最后一位是什么。如果最低位是0的话，那就可以排除最低位为1的元素；如最低位为1，那就可以排除末尾为0的。
那下一步怎么办呢？看次低位的情况？那么我以n=5，未入数组的数字为3。经过上一轮的排除后，剩下的数字如图所示：

那么现在次低位的情况为0 0 1 0 1 0 ，根据之前的逻辑我们知道，次低位应该是1。那么我们继续排除。只保留末尾为11的元素。剩下的就是：

再继续看倒数第三位。同样方法知道第三位应该是0。那么我们确定出了丢失的元素。
根据以上的方法，确定实现代码如下：

那算法的时间复杂是多少呢？第一次扫描了N次的最低位，第二次为N/2......以此类推，根据下式子：

所以我的算法的复杂度为O(n)。

 

references：

<1> http://article.yeeyan.org/view/9225/175122

<2>cracking the coding interview --Bit Manipulation