水木上看到的一个面试题,讨论很激烈

先异或下，再异或下

关键是扫描以后，对任意给出的数，都要能判定是否包含。

就是说，扫描的时候，并不知道要判定哪些数。

如果用一个位Bit来表示某一个整数是否存在，那32位的整数就需要内存 2^32/8/1024/1024 = 512MBytes
512M内存超出了题目要求。

如果不限制可以借助外部文件就好了。
可以用一个512M大小的文件，其每一位代表一个整数是否存在，扫描的时候或者判定的时候都是随即存取这个文件就可以了。

如果不借助外部文件，不太清楚怎么做。

我怎么觉得给我几个字节的内存就可以了呢?

布隆过滤器

java中整型占4字节，就是用short也要2字节，40亿个数，10m内存。。所以很显然内存是迷惑人用的，因为如果一次全加载这些数到内存肯定会内存溢出的，所以就是一个一个遍历即可

遍历，比较，设置一个临时变量保存最大的数或最小的数，遍历完后最大的数加1或最小的数减1都可以满足条件，内存不考虑jvm自身，几个字节应该够了吧

晕，不知你们所谓的扫描一遍是怎么扫？不放入内存，怎么计算？还几个字节就够了，都是牛银~

另外题目不清楚，32位的整数，意味着接近43亿的值。给出不在40亿个整数中的任意一个数？这40亿整数都是各不相同的？
给出任意一数，是给出余下的所有几亿数，还是其中任意一个？

已经是整数，没必要用bloom filter，直接用bitset，但是直接用位数组的话，内存还是问题：
40亿个数 4000000000 / 8 / 1024 / 1024大概需要500M内存
只能将40亿数分段处理了

确认一下题目的意思：
32位整数一共有：4294967296，约43亿个，40亿个整数，那就是至少有约3亿个是不在文件里的，题目的要求是求出这3亿个数中的任意一个即可，而不是全部3亿个？（3亿个本身已经超出10M内存的存储范围了）

感觉靠谱