C++ 手写 Bitset 代码模板

/ 0评 /

引言

Bitset 是一种利用对布尔数组压位存储的方法,达到优化时间常数、空间常数的目的的黑科技。利用 Bitset,可以使程序运行时间、消耗内存除以 32 或者 64(具体取决于位数,也可以在程序内调整)。在某些素质极差的卡常题中运用会有奇效。

Bitset 可以直接当做布尔数组使用,可以方便地通过 or 运算求出两个集合的并集。相较于普通的布尔数组,复杂度大大优化。

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;
    }
};

知识共享许可协议 本文章采用 知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议 进行许可。
欢迎转载,如有错误欢迎指出。
本文链接:https://skywt.cn/posts/bitset/


发表评论

电子邮件地址不会被公开。 必填项已用*标注