【算法】常见位运算总结

1.基础位运算

									0 1 0
									0 1 1
									-----
&：有0就是0							0 1 0
|：有1就是1							0 1 1
^：相同为0，相异为1  /无进位相加 		0 0 1
1
2
3
4
5
6

2. 给一个数n，确定它的二进制表示中的第x位是0还是1

n： 0 1 1 0 1 0 1 0 0 1
结论：（n >> x） & 1
1
2

3.将一个数n的二进制表示的第x位修改成1

	0 1 1 0 1 0 1 0 0 1
|	0 0 0 0 0 1 0 0 0 0
->	0 1 1 0 1 1 1 0 0 1
结论：n |= (1 << x) 
1
2
3
4

4.将一个数n的二进制表示的第x位修改成0、

	0 1 1 0 1 0 1 0 0 1
&	1 1 1 1 0 1 1 1 1 1
->	0 1 1 0 0 1 1 0 0 1
结论：n &= (~(1 << x))
1
2
3
4

5. 位图的思想

本质：哈希表

6.提取一个数(n)二进制表示中最右侧的1

	0 1 1 0 1 0 1 0 0 0
~	1 0 0 1 0 1 0 1 1 1
+1	1 0 0 1 0 1 1 0 0 0
& 	0 1 1 0 1 0 1 0 0 0
	0 0 0 0 0 0 1 0 0 0
结论：n & -n
1
2
3
4
5
6

-n：本质就是将最右侧的1，左边的区域全部变成相反

7.干掉一个数(n)二进制表示中最右侧的1

	0 1 1 0 1 0 1 0 0 
& 	0 1 1 0 1 0 0 1 1 
	0 1 1 0 1 0 0 0 0 
结论：n & (n - 1)
1
2
3
4

(n - 1)：将最右侧的1，右边的区域(包括1)全部变成相反

8.位运算的优先级

能加括号就加括号，最不容易出错！

9.异或(^运算的运算律)

1.a ^ 0 = a
2. a ^ a = 0
3. a ^ b ^ c = a ^ (b ^ c)
1
2
3