如何从40亿整数中找到不存在的一个

末蓝、 2022-04-02 13:26 222阅读 0赞

##  ##

原文地址：[从40亿个整数中找到不存在的一个][40]

## 前言 ##

给定一个最多包含40亿个随机排列的32位的顺序整数的顺序文件，找出一个不在文件中的32位整数。（在文件中至少确实一个这样的数-为什么？）。在具有足够内存的情况下，如何解决该问题？如果有几个外部的“临时”文件可用，但是仅有几百字节的内存，又该如何解决该问题？

## 分析 ##

这仍然是《编程珠玑》中的一个问题。前面我们曾经提到过《[位图法][Link 1]》，我们使用位图法解决了这个问题。32位整型最多有4294967296个整数，而很显然40亿个数中必然会至少缺一个。我们同样也可以尝试使用位图法解决该问题，使用536 870 912个字节，约512M内存存储这40亿整数，存在该整数的位置1，最后遍历比特位，输出第一个比特位为0的位置即可。那如果仅借助几个“临时”文件，使用几百字节的内存的情况下该如何处理呢？

能否使用二分搜索呢？这40亿个整数是随机排列的，因此普通的二分搜索不能找到那个不存在的数。但是我们可以基于二分搜索的思想。

一个整数有32位，我们按照每个比特位是0还是1，将要查找的数据范围一分为二。从最高比特位开始：

*  将最高比特位为0的放在一堆，为1的放在另外一堆
 *  如果一样多，则随意选择一堆，例如选0，则该位为0
 *  如果不一样多，选择少的一堆继续，如1更少，则该位为1

这里需要做一些解释：

*  由于2^32个整数中，每一个比特位是1还是0的个数是相同的。如果在这40亿个整数中，某比特位为1和0的个数是相同的，则说明两边都有不存在的数。因此选择任意一堆即可。
 *  如果比特位1的整数比0的整数多，则说明，比特位为0的一堆数中，肯定缺少了一些数。而比特位为1的一堆数中，可能缺少一些数。因此，我们选择少的，也就是比特位为0的那一堆数。
 *  每一次选择，都记录选择的是0还是1，最多32次选择后，便可以至少找到一个整数，不存在这40亿数中。

## 实例说明 ##

由于32位的整型数据量太多，不便说明，我们用一个**4比特**的数据对上面的思路再做一个说明。4比特最多有16个数。  
假设有以下源数据：

3 5 2 6 7 -1 -4 -6 -3 1 -5

对应二进制形式如下(负数在内存中以补码形式存储)：

0011 0101 0010 0110 0111 1111 1100 1010 1101 0001 1011

1.处理第1比特位被分为两部分数据，分别为：

*  比特位为0的

0011 0101 0010 0110 0111 0001

*  比特位为1的

1111 1100 1010 1101 1011

可以看到，第一比特位为1的数为5个，比比特位为0的数要少，因此选择比特位为1的数，继续处理。且第一比特位，获得**1**.

3.处理第2比特位仍然分为两部分数据，分别为：

*  比特位为0的

1010 1011

*  比特位为1的

1111 1100  1101

可以看到，第一比特位为1的数为3个，比比特位为0的数要多，因此选择比特位为0的数，继续处理。且第二比特位，获得**0**。

2.处理第3比特位仍然被分为两部分数据，分别为：

*  比特位为0的

无

*  比特位为1的

1010 1011

明显看到第三比特位为0的数没有，因此选择比特位0，获得**0**。至此，已经没有必要继续查找了。

我们最终得到了前三个比特位100，因此不存在于这些数中至少有1000,1001，即-8,-7。

## 代码实现 ##

C语言实现：

//binarySearch.c
    #include <stdio.h>
    #include <stdlib.h>
    
    #define MAX_STR 10
    #define SOURCE_FILE "source.txt" //最原始文件，需要保留
    #define SRC_FILE "src.txt"       //需要分类的文件
    #define BIT_1_FILE "bit1.txt"
    #define BIT_0_FILE "bit0.txt"
    #define INT_BIT_NUM  32
    /*
    FILE *src   源数据文件指针
    FILE *fpBit1 存储要处理的比特位为1的数据
    FILE *fpBit0 存储要处理的比特位为0的数据
    int bit     要处理的比特位
    返回值
    0：选择比特位为0的数据继续处理
    1：选择比特位为1的数据继续处理
    -1：出错
    */
    int splitByBit(FILE *src,FILE *fpBit1,FILE *fpBit0,int bit,int *nums)
    {
        /*入参检查*/
        if(NULL == src || NULL == fpBit1 || NULL == fpBit0 || NULL == nums)
        {
            printf("input para is NULL");
            return -1;
        }
        /*bit位检查*/
        if(bit < 0 || bit > INT_BIT_NUM )
        {
            printf("the bit is wrong");
            return -1;
        }
        char string[MAX_STR] = {0};
        int mask = 1<< bit;
        int bit0num = 0;
        int bit1num = 0;
        int num = 0;
        //printf("mask is %x\n",mask);
        /*循环读取源数据*/
        while(fgets(string, MAX_STR, src ) != NULL)
        {
            num = atoi(string);
            //printf("%d&%d %d\n",num,mask, num&mask);
            /*根据比特位的值，将数据写到不同的位置，注意优先级问题*/
            if(0 == (num&mask))
            {
                //printf("bit 0 %d\n",num);
                fprintf(fpBit0, "%d\n", num);
                bit0num++;
            }
            else
            {
                //printf("bit 1 %d\n",num);
                fprintf(fpBit1, "%d\n", num);
                bit1num++;
            }
        }
        //printf("bit0num:%d,bit1num:%d\n",bit0num,bit1num);
        if(bit0num > bit1num)
        {
            /*说明比特位为1的数少*/
            *nums = bit1num;
            return 1;
        }
        else
        {
            *nums = bit0num;
            return 0;
        }
    }
    /***
     *关闭所有文件描述符
     *
     * **/
    void closeAllFile(FILE **src,FILE **bit0,FILE **bit1)
    {
        if(NULL != src && NULL != *src)
        {
            fclose(*src);
            *src = NULL;
        }       
        if(NULL != bit1 && NULL != *bit1)
        {
            fclose(*bit1);
            *bit1 = NULL;
        }       
        if(NULL != bit0 && NULL != *bit0)
        {
            fclose(*bit0);
            *bit0 = NULL;
        }       
    }
    int findNum(int *findNum)
    {
        int loop = 0;
        /*打开最原始文件*/
        FILE *src = fopen(SOURCE_FILE,"r");
        if(NULL == src)
        {
            printf("failed to open %s",SOURCE_FILE);
            return -1;
        }
        FILE *bit1 = NULL;
        FILE *bit0 = NULL;
           int num = 0;
        int bitNums = 0; //得到比特位的数字数量
        int findBit = 0; //当前得到的比特位
        for(loop = 0; loop < INT_BIT_NUM;loop++)
        {
            /*第一次循环不会打开，保留源文件*/
            if(NULL == src)
            {
                src = fopen(SRC_FILE,"r");
            }
            if(NULL == src)
            {
                return -1;
            }
    
            /**打开失败时，注意关闭所有打开的文件描述符**/
            bit1 = fopen(BIT_1_FILE,"w+");
            if(NULL == bit1)
            {
                closeAllFile(&src,&bit1,&bit0);
                printf("failed to open %s",BIT_1_FILE);
                return -1;
            }
            bit0 = fopen(BIT_0_FILE,"w+");
            if(NULL == bit0)
            {
                closeAllFile(&src,&bit1,&bit0);
                printf("failed to open %s",BIT_0_FILE);
                return -1;
            }
            findBit = splitByBit(src,bit1,bit0,loop,&bitNums);
            if(-1 == findBit)
            {
                printf("process error\n");
                closeAllFile(&src,&bit1,&bit0);
                return -1;
            }
            closeAllFile(&src,&bit1,&bit0);
            //printf("find bit %d\n",findBit);
            /*将某比特位数量少的文件重命名为新的src.txt，以便进行下一次处理*/
            if(1 == findBit)
            {
                rename(BIT_1_FILE,SRC_FILE);
                num |=  (1 << loop);
                printf("mv bit1 file to src file\n");
            }
            else
            {
                printf("mv bit0 file to src file\n");
                rename(BIT_0_FILE,SRC_FILE);
            }
    
            /*如果某个文件数量为0，则没有必要继续寻找下去*/
            if(0 == bitNums)
            {
                printf("no need to continue\n");
                break;
            }
        }
        *findNum = num;
        return 0;
    }
    int main()
    {
        int num = 0;
        findNum(&num);
        printf("final num is %d or 0x%x\n",num,num);
        return 0;
    }

代码说明：

*  这里的splitByBit函数根据比特位将数据分为两部分
 *  closeAllFile用于关闭文件描述符
 *  findNum函数循环32个比特位，每处理一次得到一个比特位，最终可以得到不存在其中的整数。

利用脚本产生了约2000万个整数：

wc -l source.txt 
    20000001 source.txt

编译运行：

$ gcc -o binarySearch binarySearch.c
    $ time ./binarySearch
    final num is 18950401 or 0x1212901
    
    real    0m8.001s
    user    0m6.466s
    sys    0m0.445s

程序的主要时间花在了读写文件，且占用内存极小。

## 总结 ##

本文从一个特别的角度用最常见的二分搜索解决了该问题，最多拆分32次，便可从中找到不存在的整数。你有什么更好的思路或优化点，欢迎留言。

> 微信公众号【编程珠玑】：专注但不限于分享计算机编程基础，Linux，C语言，C++，Python，数据库等编程相关\[原创\]技术文章，号内包含大量经典电子书和视频学习资源。欢迎一起交流学习，一起修炼计算机“内功”，知其然，更知其所以然。

[40]: https://www.huyanbing.me/2018/12/25/10757.html
[Link 1]: https://www.huyanbing.me/2018/12/08/34927.html