最后更新：2014年4月30日

1、位运算包括：

这个我觉得大家都会我就随便说下：

位与&，如 101 & 110 = 100

位或|，如 100 | 110 = 110

位非~，如 ~101 = 010

位异或^，如 101 ^ 110 = 011

左移<<，如 011 << 1 = 110

右移>>，如 110 >> 1 = 011

其中，负数位运算的时候，用的是补码而不是原码请注意。

左移的时候，高位溢出的将会被舍弃，低位补0。如 11111111 << 3 = 11111000

右移的时候，低位溢出的将会被舍弃，高位补符号位。如 10000001 >> 1 = 11000000

2、gcc内置函数：

gcc中有为处理二进制而诞生的内置函数，如下：

int __builtin_ffs (unsigned int x)
返回从右往左数第一个1。其中x = 0返回0。
int __builtin_clz (unsigned int x)
返回前导0的个数。
int __builtin_ctz (unsigned int x)
返回末尾0的个数。
int __builtin_popcount (unsigned int x)
返回1的个数。
int __builtin_parity (unsigned int x)
返回1的个数的奇偶性。

3、常用技巧：

（1）lowbit = x & -x

x & -x，它把正整数x的1除了它最后一个1，都变成了0，也可以说成是取出x的最后一个1。

如lowbit(01001010) = 00000010

简单地说，对于一个数，比如01001010，它的相反数的补码为10110110，位与的结果为00000010。

原理很简单，某个正整数x的相反数的补码，等于x所有位取反，然后加1。

设y = ~x + 1，比较x和y，x的最后一个1右边都是0，y的同一个位也是1，右边也全是0（x取反加1后，最后一个1变成0，后面的0都变成1，加1后，进位，又变回来了）。而在x的最后一个1的左边和y完全相反。那么x & y就剩下x的最后一个1的位置有1，其余全是0。

这个位运算技巧在树状数组中基本上都要用到。

（2）x & (x-1) == 0 → x是2的倍数

有且只有00010000这种数，减一之后是00001111，与原数每一个位置都不同。

这个位运算的技巧可用于初始化RMQ用的Sparse Table算法。

（3）int fast_max(int x, int y) { return (((x - y) >> 31) & (x ^ y)) ^ x;}

　　int fast_min(int x, int y) { return (((y - x) >> 31) & (x ^ y)) ^ y;}

可用于快速得到x和y的最大值，比较的条件运算的速度是比较慢的（注意这个是32位有符号整数才能用，否则要修改）。

首先令z = (x - y) >> 31，若x ＜ y，有x - y ＜ 0，那么x - y的最高位为1，右移31位，得到32个位都是1的z。同理若x ≥ y，那么z = 0。

令 p = x ^ y，那么p的某一位为1当且仅当x和y的那一位不x同为1或不同为0，通俗地说，p就是x和y的“差异”。那么可以得到x ^ p = y，y ^ p = x。

那么，若x ＜ y，有z & p = p，返回值便是x ^ p = y。否则，z & p = 0，返回值为x ^ 0 = x。

4、状态压缩

所谓状态压缩，即把一个集合{0,1,……,n-1}，其中选用1表示，不选用0表示，合起来就可以用一个int的二进制表示。那么比如集合{‘a‘, ‘b‘, ‘c‘, ‘d‘}，其子集{‘b‘, ‘d‘}就可以用二进制数0101即十进制数5表示。状态压缩DP必备。

（1）测试第 i 个元素是否被选上：

bool check(int state, int i) {

　　return (state >> i) & 1;

}

（2）把第 i 个元素设为选择（即1）：

int set1(int state, int i) {

　　return state | (1 << i);

}

（3）把第 i 个元素设置为不选择（即0）：

int set0(int state, int i) {

　　return state & ~(1 << i);

}

（4）检查是否有两位选择的元素相邻：

bool check(int state) {

　　return (state & (state >> 1)) == 0;

}

5、枚举状态

　　用二进制来枚举状态，要比写一个dfs来枚举要简单快速地多。

（1）枚举{0,1,……,n-1}的所有子集：

for(int s = 0; s < 1 << n; ++s) {/*对子集s进行处理*/}

（2）枚举某个集合sup（如01101101）的子集：

像上面那样枚举判断的话，会用很多重复状态，太浪费了。

从大到小枚举，令sub = sup。每次对sub减1，然后位与sup，就能得到比原sub恰好小1的sup的子集。

int sub = sup;

do {

　　//对子集sub进行处理

　　sub = (sub - 1) & sup;

} while(sub != sup);//处理完sup = 0后，会有sup = -1

（3）枚举集合{0,1,……,n-1}的所包含的大小为k的子集：

首先得到字典序最小的子集comb = (1<<k)-1。

每次循环，取出最低位x = comb & -comb，令y = comb + x。此时x为comb的最低位的1，y把comb最低位的1开始，往左连续的1变成的0，这些1左边的第一个0变成了1。

那么~y和comb位与就得到了comb从最后一位1开始，往左的所有连续的1组成的数。

令z = ~y & comb，将z的1右移到最低位，这个用z/x可以得到，然后再右移一位，删掉最后的一个1。

最后再位与y，就把comb的最后面的连续的1的前面的0变成了1，其余的1删掉一个以后，移到最右边，就可得到comb的下一个集合。

int comb = (1 << k) - 1;

while(comb < 1 << n) {

　　//对子集comb进行处理

　　int x = comb & -comb, y = comb + x;

　　comb = ((comb & ~y) / x >> 1) | y;

}