位运算用法整理
目录
实训准备的第二弹。
简介 #
整理了一些和位运算相关的内容，主要分为以下几个部分：
- 集合的整数表示
- 位运算的常见技巧和常用公式
- gcc 中
__builtin系列函数及 C++ 中bitset类的简介
集合的整数表示 #
以下内容摘自挑战程序设计竞赛：
在程序中表示集合的方法有很多种，当元素数比较少时，像这样用二进制码来表示比较方便。集合 ${0,1,…,n-1}$ 的子集 S 可以用如下方式编码成整数。
$$ f(S)=\sum\limits_{i\in{S}}2^i $$
像这样表示之后，一些集合运算可以对应地写成如下方式。
- 空集：
0 - 只含有第 i 个元素的集合：
1<<i - 含有全部 n 个元素的集合：
(1<<n)-1 - 判断第 i 个元素是否属于集合 S：
if (S>>i & 1) - 向集合中加入第 i 个元素：
S | 1<<i - 从集合中去除第 i 个元素：
S & ~(1<<i) - 求 S 和 T 的交集、并集：
S|T, S&T
此外, 想要将集合 ${0,1,…,n-1}$ 的所有子集枚举出来的话，可以像下面这样书写：
for (int S = 0; S < (1<<n); ++S)
{
// 对子集的处理
}
按这个顺序循环的话，S 便会从空集开始，然后按照 {0},{1},{0,1},…{0,1,…,n-1} 的升序顺序枚举出来。
更高级的内容参见挑战程序设计竞赛。
其实是懒
位运算的常见技巧和常用公式 #
如有遗漏请务必补充。
- （来自: 树状数组
lowbit）取出 “从 x 的最低位的 1 直到最后” 的值：x &= -x - （来自: 线段树）快速求 $2x,2x+1$：
x<<1, x<<1|1 - （来自: 我也不知道来自哪里）把 x 最低位的 1 变成 0：
x &= (x-1) - （来自: 我也不知道来自哪里）把 x 最低位的 0 变成 1：
x |= x+1 - （来自: 状压 dp）判断 x 的第 i 位是不是 1：
if (x & (1<<i)) - （来自: 博弈论）异或（XOR）运算的性质：同一个数异或两次即为其自身
- （来自：CSAPP）C/C++ 中对于有符号数，
>>表示算术右移；对于无符号数，>>表示逻辑右移。对于两者而言，<<都表示逻辑左移。 - （来自: 为了偷懒不写 EOF）表示 x 不等于 -1：
~x。也就是说，while(scanf("%d", &n) != EOF)等价于while(~scanf("%d", &n))。
由于其中原理都不难推导，这里不再赘述。
gcc 中 __builtin 系列函数及 C++ 中 bitset 类的简介 #
这里只记录一些实训可能会用到的……
__builtin #
以下函数都返回 int，x 都为 unsigned int（当然在函数名后加 l 或 ll 可以改为 long/long long 类型）。
__builtin_popcount(x)：x 中 1 的个数__builtin_ctz(x)：x 末尾 0 的个数（x 非 0）__builtin_clz(x)：x 前导 0 的个数（x 非 0）__builtin_ffs(x)：x 中最后一个为 1 的位是从后向前的第几位__builtin_parity(x)：x 中 1 的个数模 2 的值
bitset #
本来想自己写一下，后来发现 这个博客 和 这个博客 总结得很好，就偷了个懒。
一般来说实训当中不太会有很需要用到 __builtin 和 bitset 的题目，所以了解一下就可以了。