我碰到这个面试问题，我试图了解如何解决这个问题。我读this问题的SO。我理解的帖子的作者的做法，但是我不明白接受的答案提出的办法。所以我搬到这个博客。按照这个博客，我们可以计算出0和1的数字在每个位的位置和距离，我们可以找到丢失的数量。但随后该文件应该有2 ^ 32-1号是大于4十亿。因此，该方法不应该工作的权利？我肯定没有在我的理解不对的地方，但我不能找出缺失的环节。

I came across this interview questions and I was trying to understand how to approach this problem. I read this question on SO. I understood the approach of the author of the post, however I do not understand the approach suggested in the accepted answer. So I moved to this blog. According to this blog we can calculate the number of zeroes and ones at each of the bit positions and from that we can find out the missing number. But then for that the file should have 2^32-1 numbers which is greater than 4 billion. So that method should not work right? I am sure there is something wrong in my understanding, but I just can't figure out the missing link.

推荐答案

如果你有一个从0完整的序列号为2 ^ N-1，然后在每个位的位置将等于设置的位数（和等于（2 ^ N）/ 2）。

If you had a "complete" sequence of numbers from 0 to 2^N-1 then the number of bits set in each bit position would be equal (and equal to (2^N)/2).

如果只有一个号码被丢失，那么它的1位对应于比特位置是短的一个比特计数

If only one number is missing, then it's 1 bits correspond to the bit positions that are short one bit count.

请注意，这仅适用于2的幂，但可能可以制定出更复杂的公式为奇数。

Note that this only works for powers of 2, but possibly one can work out more complex formulae for "odd" counts.