引言

Bitset 是一种利用对布尔数组压位存储的方法，达到优化时间常数、空间常数的目的的黑科技。利用 Bitset，可以方便地对布尔数组进行按位逻辑运算，优化 32 或 64 的常数。在某些素质极差的卡常题中运用会有奇效。

Bitset 可以直接当做布尔数组使用。C++ STL 中也内置了 Bitset，然而由于常数较大，不如手写的 Bitset 优秀。

代码模板

Github Link

注意：如果需要改为 64 位 Bitset，需要把 __builtin_popcount() 函数改为 __builtin_popcountll() （或者直接手写～）。

struct bitset{
    static const int maxn=35,maxm=30;
    int set[maxn];

    inline void clear(){
        memset(set,0,sizeof(set));
    }

    inline bool operator [](int index){
        index--;
        return (set[index/maxm]>>index%maxm)&1;
    }

    inline void set_value(int index,int value){
        index--;
        if (value) set[index/maxm]|=(int)1<<index%maxm; else set[index/maxm]&=~((int)1<<index%maxm);
    }

    inline void merge(bitset &b){
        for (int i=0;i<maxn;i++) set[i]|=b.set[i];
    }

    inline int count(){
        int ret=0;
        for (int i=0;i<maxn;i++) ret+=__builtin_popcount(set[i]);
        return ret;
    }
};