给定一个最多包含40亿个随机排列的32位整数的顺序文件，找出一个不在文件中的32位整数。

Question

编程珠玑里的问题：
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; 求解

Answer 1

好精妙的算法啊，太牛逼了，当时都没注意仔细看。有时间要把编程珠玑再看一遍。
re最开始是零，如果在某一位上是1的数字大于是0的数字，则把这一位的re置为0。在for循环中，将a的所有数字，按照某一位为零还是为一分成了两部分，也就是b数组和c数组，然后在后面交换b或c和a的位置，在下一个while循环里面处理数字更少的位数。re负责标记，如果某一位为1的数字更多，则这以为标记为0，如果为0的多，标记为1（什么也不做）。最后的re是一个32位的数，他的每一位都是更少的一位，所以它自己本身一定是不存在的。
这个问题本身只要求找出一个不存在的数，很好奇，能不能用这个思想找出所有不存在的数。

Answer 2

抢答！
biter <= citer 也就是说缺少的数在b数组里。所以re += v！
事实上编程珠玑里的意思是要用文件来分成两个组。
也就是首位是0放进file0, 是1则放进file1.
重复这个过程，必然找到一个缺少的数。

Answer 3

二分是对的，算法看不懂

Answer 4

我的理解是：
这里用的不是位图，应该用的是整数的二进制表示；
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;

}

Answer 5

那是不是写出 re |= v; 更好一点？即把某位置1嘛