求交集

给定两个整数集合A和B，每个集合都包含20亿个不同整数，请给出快速计算A∩B的算法，算法可使用外存，但是要求占用内存不能超过4GB。如果这里的整数是32位整数，那么每个集合用一个大小2^32位的bitmap表示，分别遍历集合算出对应bitmap后，直接遍历每一字节取交即可。每个bitmap的大小是2^32bit / 2^3(bits per Byte) = 512MB，一共使用1GB内存。构造bitmap的时候，除去bitmap还有3GB可以使用，一共可以存储3 _ 2^30 / 4 = 3 _ 2 ^28 = 8亿个整数。那每个集合要按每8亿个切分到外存中，分成3个部分。这样构造的时候每个集合读取3次外存，一共读取6次。然后如果结果交集很大而且要得到具体整数，也要对结果做切分，最多存储3次外存。