java - 给定40亿个未排序的整数，查找缺失的整数

This question already has answers here:

Find an integer not among four billion given ones
（38个答案）
我遇到了这个面试问题，我试图理解如何解决这个问题。我读了很多问题。我理解文章作者的方法，但是我不理解接受的答案中建议的方法。所以我转到了这个this。根据这个博客，我们可以计算每个位位置的0和1的个数，从中我们可以找出丢失的个数。但是对于这个文件应该有2^32-1个大于40亿的数字。所以这种方法不应该奏效？我确信我的理解有问题，但我就是想不出缺少的环节。

最佳答案

如果您有一个从0到2^N-1的“完整”数字序列，那么在每个位位置设置的位数将等于（并且等于（2^N）/2）。
如果只缺少一个数字，那么它的1位对应于短1位计数的位位置。
请注意，这只适用于2的幂，但可能有人可以计算出更复杂的“奇数”计数公式。