与哈希表有点类似, 可以更高效的将一个数字放入位图中, 判断一个数是否存在, 以及移除一个数.

原理是用N位二进制, 从最低位开始, 每一位表示一个数是否存在. 比如:

1001, 表示位图中有0, 没有1, 没有2, 有3.

class BitSet {
    vector<int> v;
public:
    BitSet(int n) { // 位图最大容量为, 存储0~n-1这几个数
        v.resize((n + 32 - 1) / 32); // v的每个格子有32位, 每个格子能存储32个数, 因为要存储n个数, 共需要 n / 32 向上取整个格子
    }
    
    void add(int val) {
        int bucket = val / 32;
        int indexOfBucket = val % 32;
        v[bucket] = v[bucket] | (1 << indexOfBucket);
    }
    
    void remove(int val) {
        int bucket = val / 32;
        int indexOfBucket = val % 32;
        v[bucket] = v[bucket] & (~(1 << indexOfBucket));
    }
    
    void flip(int val) { // 原来有val, 设为没有, 原来没有val, 设为有
        int bucket = val / 32;
        int indexOfBucket = val % 32;
        v[bucket] = v[bucket] ^ (1 << indexOfBucket);
    }
    
    bool contain(int val) {
        int bucket = val / 32;
        int indexOfBucket = val % 32;
        return ((v[bucket] >> indexOfBucket) & 1) == 1;
    }
};
`