5/14-5/20 CareerCup 5.7

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?

https://github.com/writecoffee/career_cup_iteration/blob/improved/5.7.cpp


//////////////////////////////////////////////////////////////////////////////////////
// GIST
// 1.        since the array starts from zero, in the LSB, originally bit-0 amount should
//        be at least equivalent to that of bit-1
// 2.        based on the above statement, every time 'imbalence' occurs (i.e. when one of
//        the 0-bits was removed, bit-1 amount would be bigger or equals to that of the
//        bit-0; on the opposite, when one of the 1-bits was removed, bit-0 amount just
//        naturally bigger than that of the bit-1) we can get the missing bit and
//        eliminate half the array elements where the opposite bit exists
// 3.         recurse step-2 from LSB to MSB repeatedly
// (4.)        when array becomes empty, fill up 0-bit in the front of the binary result
//
// TIME_COMPLEXITY
//         at each level, we need (N-1) / 2^lev operations, 'width' levels combined is
//        2N, namely O(N)
////////////////////////////////////////////////////////////////////////////////////

https://gist.github.com/3156330

感觉这个应该比答案好
https://github.com/0x7ffff/Career-Cup-archive/blob/master/5/7.c

比如n=5, miss=3, 那把数组里的元素和［0-5］通通xor一遍，结果就是3了
0^1^2^3^4^5^5^4^1^2 = 3