给40亿个不重复的无符号整数，没排过序。给一个无符号整数，如何快速判断一个数是否在这40亿个数中。【腾讯】

待我称王封你为后i 2022-06-14 09:59 159阅读 0赞

40亿占多少个字节：4G  
10个亿需要1G  
一个整型需要4个字节，40亿个则需要16G  
由于如果我们直接使用这种方式去存储需要16个G显然这是不可能的，因此我们需要用到下面的方式去存储，采用位图  
我们用一个Bit位去标识一个数存在还是不存在  
我们都是到一般字节是存储的最小单位  
那么一个字节有8个位，巧妙的利用这一点来实现我们的位图  
比如10我们先确定他存在第几个字节，再去确定它在第几个字节的第几个位上

如果是40亿个整型，那么我们大概实际上需要多少个字节？  
我们由于一个整型采用一个字节上的一个位就可以存储。

#include<iostream>
    #include<stdlib.h>
    #include<vector>
    using namespace std;
    class BitMap
    {
    public:
        BitMap(size_t range)
        {
            _bitmap.resize(range >> 3);
        }
        void Set(int num)
        {
            int index = num >> 3;//确定在第几个字节
            int pos = num % 8;
            _bitmap[index] |= 1 << pos;
        }
        void Reset(int num)
        {
            int index = num >> 3;
            int pos = num % 8;
            _bitmap[index] &= ~(1 << pos);
        }
        bool Test(int num)
        {
            int index = num >> 3;
            int pos = num % 8;
            return _bitmap[index] &= 1 << pos;
        }
    protected:
        vector<char> _bitmap;
    };
    int main()
    {
        BitMap bm(-1);
        bm.Set(10);
        bm.Set(10555);
        bm.Set(12222);
        bm.Set(16666);
        bm.Reset(10);
        cout<<bm.Test(10)<<endl;
        cout<<bm.Test(10555)<<endl;
        cout<<bm.Test(12222)<<endl;
        cout<<bm.Test(16666)<<endl;
        system("pause");
        return 0;
    }

很明显我们的位图的确是节省了大量的空间，但是位图也有它的缺点，它只能处理整型的数据。