【OI】位运算操作

一、基础操作

1.a<<b

将二进制a左移b位,不够的地方用0补位

例如

100<<2 == 10000

2.a>>b

将二进制a右移b位

例如

100>>2 == 1

3.a|b

或操作（按位或），相同位中只要有一个1或者两个1则结果为1，全0则结果为0

4.a&b

与操作（按位与），相同位中只要都是1，则结果为1，如果一个为0一个为1或者都是0则结果为0。

5.a^b

异或，相同位只要一个1一个0，则结果为1；相同位二进制相同则结果为0 。

二、进阶操作

1.快速求2^n

1<<n == pow(2,n)

原理：1<<n的意思是1的二进制向左移动n位，则此数二进制形式变成了 100000...000(n个0)，恰好是2^n

2.判断奇数偶数

n&1 == 1则为奇数

n&1 == 0则为偶数

原理：n&1的意思是n与1，那么n与1中，1除了右端位为1其他位都是0，则由与运算得到的结果中其他位必定都是0 。

所以最后得到的结果只与1的右端位和n的右端位有关，我们知道1的右端位为1，那么n的右端位只有为1的时候与1进行与运算的结果是1；n的右端位只有为0的时候与1进行与运算的结果是0 。

显然二进制右端位为1的时候该数为奇数，为0时该数为偶数，所以得证。

3.lowbit

a&(-a) 代表着a的二进制的最后一位。

原理：涉及到二进制的补码知识，感兴趣的人可以自己了解。

三、高阶操作

1.a >> b & 1 代表着如果a的第b位为1则为真

用来判断二进制的某一位

原理：a左移b位，则a的右端位就是原来a的第b位，这时与1做与运算(1左边的0由与运算性质得没有影响)就可以得知这一位是1还是0（1&1 == 1,0|1 == 0 ）

2.a|(1<<n) 代表着将a的二进制的第n位设为1

原理：1<<n可以看作由一个1和n个0组成的二进制数，其中0的部分由或的性质(0|0==0,1|0==1)可以知道不会对二进制位产生影响。

而1的部分由或的性质(1|1==1,0|1=1)可以得出一定是1。

四、图论

x表示要判断的点，S表示集合

(1 << x) & S == true 即x在S集合里，如果为false则x不在S集合里

S = S | (1 << x) 表示S集合中加入了x点

巴特西