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


### 5 条评论

围观毒瘤.png

#### 【算法】 NOIP 简单的代码优化和编程技巧 – K-XZY · 2018年10月11日 8:05 下午

[…] 据说可以用 bitset+分块+可持久化过静态仙人掌，不过我是完全看不懂 Orz。接着最后我们再来 Orz 一下 Cai dalao 的手写 bitset tql […]

#### 【算法】简单的常数优化和编程技巧 —B_Z_B_Y – K-XZY · 2018年10月10日 5:55 下午

[…] 如何卡常，再可以看看 XZYdalao 的手写 bitset) tql […]