BitSet位图

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

思路：如果内存够的话，40亿个整型使用位图存储需要500M左右的空间。

代码：

#pragma once
#include <vector>

class BitMap
{
public:
    BitMap()
        :_size(0)
    {}
    BitMap(size_t n)
        :_size(0)
    {
        _array.resize((n>>5) + 1);
    }
    bool Test(size_t num)//查看此数是否存在
    {
        size_t index = num>>5;
        size_t n = num % 32;

        return _array[index]&(1<<n);
    }
    bool Set(size_t num)
    {
        size_t index = num>>5;
        size_t n = num % 32;
        if(_array[index] & (1<<n))//这个数已经存在了
        {
            return false;
        }
        _array[index] |= 1<<n;//注意这里，右移时是向其高位移动，并不是真的向右移动。
        _size++;
        return true;
    }
    bool Reset(size_t num)
    {
        size_t index = num>>5;
        size_t n = num % 32;
        if(!_array[index] & (1<<n))//这个数不存在
        {
            return false;
        }
        _array[index] &= ~(1<<n);
        _size--;
        return true;
    }

    void Clear()
    {
        _array.assign(_array.size(),0);
    }
protected:
    vector<size_t> _array;
    size_t _size;
};

测试：

#include <iostream>
using namespace std;
#include "BitSet.h"

void test()
{
    BitMap bm1(100);
    bm1.Set(1);
    bm1.Set(33);
    bm1.Set(69);
    bm1.Set(100);

    bm1.Reset(33);
}
int main()
{
    test();
    return 0;
}

注：给四十亿个数时，可以用BitMap(-1).