【模板】手写 bitset

比 STL 自带的 bitset 快很多。

#define FOR(i, l, r) for(int i = (l), i##_end = (r); i <= i##_end; ++i)
#define REP(i, l, r) for(int i = (l), i##_end = (r); i <  i##_end; ++i)
#define DFR(i, l, r) for(int i = (l), i##_end = (r); i >= i##_end; --i)
#define DRP(i, l, r) for(int i = (l), i##_end = (r); i >  i##_end; --i)

unsigned int BitReverse(unsigned int x) {
    static unsigned int a[1 << 16 | 1], now = 1;
    if(now) {
        a[0] = now = 0;
        REP(i, 1, 1 << 16) a[i] = (a[i >> 1] >> 1) | ((i & 1) << 15);
    }
    return a[x >> 16] | (a[x & 65535] << 16);
}

int BitNum(unsigned int x) {
    static unsigned int a[1 << 16 | 1], now = 1;
    if(now) {
        a[0] = now = 0;
        REP(i, 1, 1 << 16) a[i] = a[i >> 1] + (i & 1);
    }
    return a[x >> 16] + a[x & 65535];
}

struct bitset {
    static const int BIT = 32;
    static const int SIZE = SN / BIT;
    unsigned int a[SIZE];

    bitset();

    unsigned int & operator [] (const int);
    const unsigned int & operator [] (const int) const;

    bitset operator & (const bitset &) const;
    bitset operator | (const bitset &) const;
    bitset operator ^ (const bitset &) const;
    bitset operator << (int) const;
    bitset operator >> (int) const;

    bitset & operator &= (const bitset &);
    bitset & operator |= (const bitset &);
    bitset & operator ^= (const bitset &);
    bitset & operator <<= (int);
    bitset & operator >>= (int);

    bitset operator ~ () const;

    // reverse the binary bit in [0, x)
    // "000110010".Reverse(5) = "000001001"
    bitset Reverse(int x) const ;

    // set the xth binary bit value to f
    void Set(int x, bool f = true); 

    // set all binary bit value to 0
    void Clear();

    // return the xth binary bit value
    bool CheckBit(int x) const ;

    // return the number of one in binary bit value
    int AllBit() const;
};

bitset::bitset() {memset(a, 0, sizeof a);}

unsigned int & bitset::operator [] (const int x) {
    return a[x];
}

const unsigned int & bitset::operator [] (const int x) const {
    return a[x];
}

bitset bitset::operator & (const bitset &x) const {
    bitset ans;
    REP(i, 0, SIZE) ans[i] = x[i] & a[i];
    return ans;
}

bitset bitset::operator | (const bitset &x) const {
    bitset ans;
    REP(i, 0, SIZE) ans[i] = x[i] | a[i];
    return ans;
}

bitset bitset::operator ^ (const bitset &x) const {
    bitset ans;
    REP(i, 0, SIZE) ans[i] = x[i] ^ a[i];
    return ans;
}

bitset bitset::operator << (int x) const {
    bitset ans;
    int y = x >> 5, z = x & 31;
    if(z) 
        DFR(i, SIZE - 1, y + 1)
            ans[i] = (a[i - y] << z) | (a[i - y - 1] >> (BIT - z));
    else
        DFR(i, SIZE - 1, y + 1)
            ans[i] = a[i - y];
    ans[y] = a[0] << z;
    return ans;
}

bitset bitset::operator >> (int x) const {
    bitset ans;
    int y = x >> 5, z = x & 31;
    if(z)
        REP(i, 0, SIZE - y - 1)
            ans[i] = (a[i + y] >> z) | (a[i + y + 1] << (BIT - z));
    else
        REP(i, 0, SIZE - y - 1)
            ans[i] = a[i + y];
    ans[SIZE - y - 1] = a[SIZE - 1] >> z;
    return ans;
}

bitset & bitset::operator &= (const bitset &x) {
    REP(i, 0, SIZE) a[i] &= x[i];
    return *this;
}

bitset & bitset::operator |= (const bitset &x) {
    REP(i, 0, SIZE) a[i] |= x[i];
    return *this;
}

bitset & bitset::operator ^= (const bitset &x) {
    REP(i, 0, SIZE) a[i] ^= x[i];
    return *this;
}

bitset & bitset::operator <<= (int x) {
    int y = x >> 5, z = x & 31;
    if(z)
        DFR(i, SIZE - 1, y + 1)
            a[i] = (a[i - y] << z) | (a[i - y - 1] >> (BIT - z));
    else
        DFR(i, SIZE - 1, y + 1)
            a[i] = a[i - y];
    a[y] = a[0] << z;
    REP(i, 0, y) a[i] = 0;
    return *this;
}

bitset & bitset::operator >>= (int x) {
    int y = x >> 5, z = x & 31;
    if(z)
        REP(i, 0, SIZE - y - 1)
            a[i] = (a[i + y] >> z) | (a[i + y + 1] << (BIT - z));
    else
        REP(i, 0, SIZE - y - 1)
            a[i] = a[i + y];
    a[SIZE - y - 1] = a[SIZE - 1] >> z;
    REP(i, SIZE - y, SIZE) a[i] = 0;
    return *this;
}

bitset bitset::operator ~ () const {
    bitset ans;
    REP(i, 0, SIZE) ans[i] = ~a[i];
    return ans;
}

bitset bitset::Reverse(int x) const {
    bitset ans;
    int y = x >> 5, z = x & 31;
    FOR(i, 0, y) ans[i] = BitReverse(a[y - i]);
    return ans >> (BIT - z);
}

void bitset::Set(int x, bool f) {
    int y = x >> 5, z = x & 31;
    a[y] |= 1 << z;
    if(!f) a[y] ^= 1 << z;
}

void bitset::Clear() {
    memset(a, 0, sizeof a);
}

int bitset::AllBit() const {
    int ans = 0;
    REP(i, 0, SIZE) ans += BitNum(a[i]);
    return ans;
}

bool bitset::CheckBit(int x) const {
    int y = x >> 5, z = x & 31;
    return a[y] >> z & 1;
}