Find The missing number in range [0,n]
Compare all the Least Significant bits, 
and either there are less ones or zeroes.

We continue this search only on the set where there is less of some bit, half the input at each iteration.

$$n + \frac{1}{2}n + \frac{1}{4}n + ... &lt; 2n.$$

And we accumulate the missing bits at each step, to come to the missing number.

So the running time is $O(n)$.