位向量

位向量是一个简单且很有用的数据结构，在充分利用小空间存储大量数据方面非常有优势。

#define POS(x)     ((x) >> 5)
#define MASK(x)    (1 << ((x) & 31))

#define MAXN   100000
int bitset[1 + POS(MAXN)] = {0};

void set(int i) {
    bitset[POS(i)] |= MASK(i);
}
void clr(int i) {
    bitset[POS(i)] &= ~MASK(i);
}
void flip(int i) {
    bitset[POS(i)] ^= MASK(i);
}
int test(int i) {
    return bitset[POS(i)] & MASK(i);
}

STL中提供了现成的bitset接口，常用的方法列出如下：

bitset<N> bs;    // declare a bitset with size N
bs.size();       // returns the number of bits in bs
bs.count();      // returns the number of bits that are set (to true)
bs.any();        // test if any bit is set
bs.none();       // test if no bit is set
bs.all();        // test if all bits are set
bs[i];           // set i-th bit to false
bs.set();        // set all bits to true
bs.reset();      // set all bits to false
bs.flip();       // flip all bits
bs.flip(i);      // flip i-th bit