bitset

bitset是像bool数组一样的东西。但每个位置只占1bit。
一定程度上节省了空间和时间，一般来说会让算法复杂度/32。

定义与初始化：

• 头文件：#include<bitset>
• 定义时需指明所占用的空间（类数组）：bitset<114514>bit;
• 初始化可以用string或int（整数类型）：

bitset<23>bit (string("11101001"));
bitset<23>bit = 233;

常用函数：

bit.size()      返回大小（位数）
bit.count()     返回1的个数
bit.any()       返回是否有1
bit.none()      返回是否没有1
bit.set()       全都变成1
bit.set(p)      将第p + 1位变成1（bitset是从第0位开始的！） 
bit.set(p, x)   将第p + 1位变成x
bit.reset()     全都变成0
bit.reset(p)    将第p + 1位变成0
bit.flip()      全都取反
bit.flip(p)     将第p + 1位取反
bit.to_ulong()  返回它转换为unsigned long的结果，如果超出范围则报错
bit.to_ullong() 返回它转换为unsigned long long的结果，如果超出范围则报错
bit.to_string() 返回它转换为string的结果

杂stl

• rotate ：用于vector

rotate(a, b, c) 把 b ~ c 的元素放到 a 前面。 把[a ~ b) 和 [b, c) 互换

• 高效位运算

__builtin_ffs (unsigned int x)返回x的最后一位1的是从后向前第几位，比如7368（1110011001000）返回4

__builtin_clz (unsigned int x)返回前导的0的个数。

__builtin_ctz (unsigned int x) 返回后面的0个个数，和; builtin_clz相对。

__ builtin_popcount (unsigned int x) 返回二进制表示中1的个数。

__builtin_parity (unsigned int x) 返回x的奇偶校验位，也就是x的1的个数模2的结果。