find the missing integer

An array A[1 . . n] contains all the integers from 0 to n except one. It would be easy to determine the missing integer in O(n) time by using an auxiliary array B[0 . . n] to record which numbers appear in A. In this problem, however, 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 j th bit of A[i],” which takes constant time.

Show that if we use only this operation, we can still determine the missing integer in O(n) time.