bitset

1
2
3
4
5
6
7
8
9
10
11
biset<32> s(10);  //32位的bitset,赋值为十进制的10
bitset<32> bs("011010101001"); //用字符串初始化
bs[20]=1; //像数值一样对某一位进行操作

s=10; //赋值为十进制的10
s.reset();//清零
s.set(); //全部位置放置为1
s.count(); //统计1的个数

b.flip(); //把b中所有二进制位逐位取反
b.to_ulong();//用b中同样的二进制位返回一个unsigned long值

builtin函数

LINK glibc的位运算函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int __builtin_ffs (unsigned int x)
//返回右起第一个‘1’的位置。

int __builtin_clz (unsigned int x)
//返回左起第一个‘1’之前0的个数。

int __builtin_ctz (unsigned int x)

//返回右起第一个‘1’之后的0的个数。

int __builtin_popcount (unsigned int x)

//返回‘1’的个数。

int __builtin_parity (unsigned int x)

//返回‘1’的个数的奇偶性。

连续整数区间的异或

记f(a,b)为区间[a,b]内连续整数的异或值。

一些结论:

  • f(0,2^k-1)=0;
  • (a xor b) xor b = a
  • 0 xor a = a

推导:

$$\begin{align}
&对于n \ge 4,\;f(0,n)=f(0,2^k-1) xor f(2^k,n)=f(2^k,n) \,\,\,\, 2^k \le n < 2^{k+1}-1 \\
\\
&2^k到n共有 n-2^k+1 个数且第k位(最高位)均为1,忽略最高位,讨论n: \\
&if\,\, Odd(n):\,\, f(0,n)=f(2^k,n)=f(0,n-2^k) \Rightarrow f(0,n)=f(0,n\,mod\,4) \\
&if\,\, Even(n):\,\, f(0,n)=f(2^k,n)=f(0,n-2^k) xor 2^k \Rightarrow f(0,n)=f(0,n\,mod\,4)\,\, xor\,\, (2^k \,\,xor\,\, n-n\,mod\,4) \\
\\
&f(0,n)=f(1,n)=\begin{cases}
n &n\,mod\,4=0 \\
1 &n\,mod\,4=1 \\
n+1 &n\,mod\,4=2 \\
0 &n\,mod\,4=3
\end{cases} \\
\\
&f(a,b)=f(0,b) \,\,xor\,\, f(0,a-1)
\end{align}
$$

应用:

  • 博弈论Nim游戏中状态的求解

枚举子集

1
2
//s为全集
for(int i=s; i ; i=(i-1)&s)

1的个数固定的字典序枚举

1
2
3
4
5
uint next(uint x) //获得当前x(x中有k个1)的字典序下一位
{
uint l = x & -x, y = x + l;
return y | (((x^y) / l) >> 2);
}

注意

  • 位运算优先级较低,所以记得加括号,不然会出现 d[1<<20+10]…这样的悲剧