描述:
编程珠玑里的问题：
A题：给定一个最多包含40亿个随机排列的32位整数的顺序文件，找出一个不在文件中的32位整数。
3、如果内存不足，仅可以用文件来进行处理，如何处理？
文中指出用二分法， 看到一段代码是这样写的（http://www.2cto.com/kf/201205/131442.html）：
int split(int* a, int* b, int*c, int alen, int bit)
{
int biter, citer, i;
int v=0, re = 0, *t;
while(bit--){
v = (1 << bit);
for(i=biter=citer=0; i < alen; i++) {
if(a[i] & (1<<bit)) {
b[biter++] = a[i];
} else {
c[citer++] = a[i];
}
}
if(biter <= citer) {
re += v;
t = a;
a = b;
b = t;
alen = biter;
} else {
t = c;
c = a;
a = t;
alen = citer;
}
}
return re;
}
说明： a, b, c,都是三个等长的数组，alen表示其长度。bit表示位数。比如32位。bit=32.
re表示最后缺少的那个数。
问题： 为什么是 re += v;， v = 1 << bit, 也就是2的bit次方, 用re累加v意义是纳尼， bitmap不是通过位置来表示value吗，比如00000...1000表示的是4，搞不懂这里的re += v; 求解
解决方案1:
我的理解是：
这里用的不是位图，应该用的是整数的二进制表示；
a指向待查找数组，b存储特定某位为1的的数， c存储某位为0的数；
int split(int* a, int* b, int*c, int alen, int bit)
{
int biter, citer, i;//biter、citer分别是b和c的索引计数器
int v=0, re = 0, *t;
while(bit--){
v = (1 << bit); //v从最高位开始依次向后
for(i=biter=citer=0; i < alen; i++) { //遍历数组a
if(a[i] & (1<<bit)) {
b[biter++] = a[i];//若a[i]的第bit位为1，就把它存入b中
} else {
c[citer++] = a[i];//若a[i]的第bit位为0，则存入c中
}
}
if(biter <= citer) {//在遍历第bit位中，bit位为1的数比bit位为0的数少，那么缺失值肯定
//在bit位为1的中（在b中）
re += v; //所以将待求值第bit位置1
t = a;
a = b;
b = t; //我觉得这里将b给a就行了，没必要交换
alen = biter;
} else {
t = c; //若c数量少，则缺失值第bit为0，不用处理
c = a;
a = t; //将c赋给a，进行下一次迭代
alen = citer;
}
}
return re;
}
解决方案2:二分是对的，算法看不懂
解决方案3:抢答！
biter <= citer 也就是说缺少的数在b数组里。所以re += v！
事实上编程珠玑里的意思是要用文件来分成两个组。
也就是首位是0放进file0, 是1则放进file1.
重复这个过程，必然找到一个缺少的数。
好精妙的算法啊，太牛逼了，当时都没注意仔细看。有时间要把编程珠玑再看一遍。
re最开始是零，如果在某一位上是1的数字大于是0的数字，则把这一位的re置为0。在for循环中，将a的所有数字，按照某一位为零还是为一分成了两部分，也就是b数组和c数组，然后在后面交换b或c和a的位置，在下一个while循环里面处理数字更少的位数。re负责标记，如果某一位为1的数字更多，则这以为标记为0，如果为0的多，标记为1（什么也不做）。最后的re是一个32位的数，他的每一位都是更少的一位，所以它自己本身一定是不存在的。
这个问题本身只要求找出一个不存在的数，很好奇，能不能用这个思想找出所有不存在的数。