首页 > 代码库 > 一个文件中有40亿个整数,每个整数为四个字节,内存为1GB,写出一个算法:求出这个文件里的整数里不包含的一个整数

一个文件中有40亿个整数,每个整数为四个字节,内存为1GB,写出一个算法:求出这个文件里的整数里不包含的一个整数

4个字节表示的整数,总共只有2^32约等于4G个可能。
为了简单起见,可以假设都是无符号整数。
分配500MB内存,每一bit代表一个整数,刚好可以表示完4个字节的整数,初始值为0。基本思想每读入一个数,就把它对应的bit位置为1,处理完40G个数后,对500M的内存遍历,找出一个bit为0的位,输出对应的整数就是未出现的。
算法流程:
1)分配500MB内存buf,初始化为0
2)unsigned int x=0x1;
  for each int j in file
  buf=buf|x<<j;
  end
(3) for(unsigned int i=0; i <= 0xffffffff; i++)
  if (!(buf & x<<i))
  {
  output(i);
  break;
  }
以上只是针对无符号的,有符号的整数可以依此类推。