位图

[bosthhe1]

首先我们知道哈希映射的条件必须是非负和整数，无符号数的范围是1~2^32,如果我们使用int来存储数据的话，需要开160亿多个字节，就是16G的空间，所以为了节省空间，就使用bity位的位置来代表这个数是否存在，bity只需要开42亿9千万个bity就行，所以就是500M左右，我们以char为例子，一个char为8个bity，所以一个char能存放8个数据，两个char就能存放16个数据[0,15],如果这些数据存在我们则把对应的0的位置变为1，所以在位图中，char的值并没有实际意义，我们只需要计算数的前面有几个bity，就能得到这个数的值

[bosthhe1]

template<size_t N>//模板的参数只能为整型
    class Bitmap
    {
    public:
        Bitmap()
        {
            arr.resize(N,0);
        }
        void set(size_t x)//将对应位置设置为1
        {
            int i = x / 8;
            int j = x % 8;
            arr[i] |= (1 << j);
        }
        void reset(size_t x)//将对应位置设置为0
        {
            int i = x / 8;
            int j = x % 8;
            arr[i] &= ~(1 << j);
        }
        bool find(size_t x)//查找
        {
            int i = x / 8;
            int j = x % 8;
            if (arr[i] &= (1 << j))
                return true;
            return false;
        }
    private:
        vector<char> arr;
    };