题目：
给定一个输入文件，包含40亿个非负整数，请设计一种算法，产生一个不在该文件中的整数。假定你有1GB内存来完成这个任务。
一、几个数字
1、40亿==4*109~~22*230==232，也就是说整数就这么多个
2、1GB==230B==8*230b~~80亿，也就是说如果用一位表示一个整数，可以表示80亿个整数（虽然没有这么多）
二、需要用到的C++基础知识
1、byte类型：byte并不是C++数据类型的关键字，如果希望使用byte类型，可以用unsigned char类型（8位）
2、unsigned char 与 char的区别，char类型的首位代表的正负号，所以取值是-128~127。
3、求类型的最大值 https://msdn.microsoft.com/en-us/library/296az74e(VS.80).aspx
1 #include<iostream> 2 using namespace std; 3 void main() 4 { 5 cout<<INT_MAX<<endl; 6 cout<<CHAR_MAX<<endl; 7 cout<<UCHAR_MAX<<endl; 8 }
4、读文件操作
1 #include<iostream> 2 #include<fstream> 3 using namespace std; 4 void main() 5 { 6 ifstream infile; 7 infile.open("data.txt"); 8 if(!infile){ 9 cerr<<"error:unable to open input file: "<<infile<<endl; 10 return; 11 } 12 char s[10]; 13 while(!infile.eof()) 14 { 15 infile.getline(s,' '); 16 cout<<s<<endl; 17 } 18 }
5、位操作
<< ：左移符号 —— 1<<2 ——> 00000001<<2 ——> 00000100（相应的>>）
&：与操作，都为1取1，其余为0 01010101 & 00001111==00000101（相应的|和 ^）
+：注意区分一下'+'和'&'，'+' 是求和，逢2进1
三、位向量
向量，vector，在Java里面就是一种大小可改变的数组
位向量，首先是一个向量（数组），每个元素占用1位的内存空间，存放的是0和1。
四、问题解决
1、思路：按照最开始的分析，如果用一位代表一个整数，那么1G内存完全可以放下
（1）创建一二包含40亿个比特的位向量BV（采用的是byte严格来讲不叫位向量吧）
（2）将BV的元素初始化为0
（3）扫描文件中的所有数字，将代表当前数字的为置为1
（4）从头遍历BV，返回第一个值为0的索引
2、数据类型采用的是byte，byte类型占8位，因此可以代表8个整形数字，给定一个数，如何计算它的位置？
byte []bv = new byte[num]
0：在第一个元素的第8位
7：在第一个元素的第1位
10：10>7，所以第一个元素没有它的位置了，它在第二个元素的第三位
...
对任一个整数n，它所在的位置为byte[n/8]的第1<<n%8位，大概是这样的赶脚：
7 6 5 4 3 2 1 0 , 15 14 13 12 11 10 9 8,.....
那给定一个位置，如上，求它代表的数字，即byte[i][1<<j]（就先这样表示了）
byte[0][1<<4] = i*8+4 = 4
byte[1][1<<[1<<5]=1*8+5 = 13
3、代码
1 #include<iostream> 2 #include<fstream> 3 using namespace std; 4 void main() 5 { 6 ifstream infile; 7 infile.open("data.txt"); 8 if(!infile){ 9 cerr<<"error:unable to open input file: "<<infile<<endl; 10 return; 11 } 12 char s[10]; 13 int temp=0; 14 unsigned int nInts = INT_MAX+1; 15 cout<<nInts<<endl; 16 unsigned char *bv = new unsigned char(nInts/8); 17 while(!infile.eof()) 18 { 19 infile.getline(s,' '); 20 //cout<<typeid(s).name(); 21 temp=atoi(s); 22 cout<<temp<<endl; 23 bv[temp/8] |= 1<<(temp%8); 24 } 25 for(int i=0;i<sizeof(bv);i++){ 26 for(int j=0;j<8;j++){ 27 if(((bv[i]>>j)&1) == 0){ 28 cout<<"result:"<<i*8+j<<endl; 29 return; 30 } 31 } 32 } 33 }
为了写出这段代码真是要了亲命了......
我用古老的VC6.0运行的会报错误，但是结果还是算出来了，一定是VC的问题，嗯...
但是我没有用海量的数据去测试
这道题的思路和解法参考的是《面试金典》上的一道题，只不过我改成了C++版本，
而且貌似它给的代码有些小bug，第18行的判断，未实验，感觉是....反正我的版本改了。
五、进阶：只能使用10MB内存
遇到这种问题的时候，虽然我不保证能做出来，但是会这样去想：
给了数据量和内存，先大概估算一下内存能否放的下：
（1）可以放下，最简单的就是排序求解了
（2）放不下，那就分而治之，划分为不同的子文件，分别求解
但是现在好像可以这样想：
（2）放不下，但是可以用位向量表示，位向量放的下，就可以用位向量求解
（3）不能用位向量或者位向量也放不下，那就只能另寻他法了。
对于这道题，我的第一反应也是划分子文件，再求解，但是看到了另一种差不多的方法...
思路：
显然现在这种情况（1）（2）都不行了，只能划分。
10MB=10*220B~223B————221个整数
所以划分为每块可以存储221个整数的区块
区块的个数：232/221=211——2000块
怎么个意思呢：
稍微调节一下，区块大小220，块数212
（1）首先扫描整个文件
如果属于区间[0,220-1]，区块1++；如果属于[220,221-1]，区块2++...
（2）各个区块，看各个区块的值是多少
如果值<220,此区块一定少元素
（3）在少数字的区块通过前述位向量的方法计算
问题：
因为存在重复数字，万一正好每个区间都不少呢？就只能对每一个区块都进行位向量计算吗？