C++ 手写 Bitset 代码模板

引言

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