位运算(bitwise)

计算机底层是使用二进制形式存储数据的，每一位是1或者0，因此当我们在某些场景使用位运算的时候，效率会更高一些。

• 与运算：同1为1，否则为0

0 & 0 = 0
0 & 1 = 0
1 & 0 = 0
1 & 1 = 1

• 或运算：同0为0，否则为1

0 | 0 = 0
1 | 0 = 1
0 | 1 = 1
1 | 1 = 1

• 异或：相同为0，不同为1

0 ^ 0 = 0
0 ^ 1 = 1
1 ^ 0 = 1
1 ^ 1 = 0

• 移位

• 取反

~0 = 1

比较常用的位运算

		解释
	x ^ 0 = x	任何数与0异或，结果都是它本身
	x ^ x = 0	任何数与它本身异或，结果都是0
	x ^ 1s = ~x (1s为全1)	一个数和全1异或，相当于取反
	x ^ (~x) = 1s	一个数和它取反后的结果异或，结果为全1
	c = a ^ b => a ^ c = b, b ^ c = a	交换两个数
	a ^ b ^ c = a ^ (b ^ c) = (a ^ b) ^ c	加法（异或）结合律

示例
1100 ^ 0000 = 1100
1100 ^ 1100 = 0000
1100 ^ 1111 = 0011 （~1100 = 0011）
1100 ^ 0011 = 1111

		解释
	x & (~0<<n)	将x最右边的n位清零
	(x>>n) & 1	获取x的第n位值（0或者1）
	x & (1<<n)	获取x的第n位的幂值
	x 丨 (1<<n)	仅将第n位置为1
	x & ((1<<n) - 1)	将x最高位至第n位（包含）清零
	x & (~(1 << n))	仅将第n位置为0

示例（都只用四位） ， 假设n = 2, x = 1101
~0 = 1111，1111 << 2 = 1100， 1101& 1100 = 1100
即将x的第n位移到最低位，和1做与运算：1101 >> 2 = 0011，0011 & 0001 = 1
即将1移到n的位置，和x做与运算：1 << 2 = 0100， 1101 & 0100 = 0100
即将1移到n的位置，和x做或运算：1 << 2 = 0100，1101 | 0100 = 1101
即将x与n之后为全1的数做与运算：1 << 2 = 0100，0100 - 1 = 0011，1101 & 0011 = 0001
即将x与一个除了第n位之外全是1的数做与运算：1 << 2 = 0100，~0100 = 1011，1101 & 1011 = 1001

	解释
x % 2 == 1 ----> (x & 1) == 1	奇数判断
x % 2 == 0 ----> (x & 1) == 0	偶数判断
x >> 1---->x / 2	一个数右移1位，相当于对2取模
x = x & (x - 1)	清零最低位的1
x & -x	得到最低位的1
x & ~x => 0	一个数和它的取反结果做与运算，结果为0

一些练习题

	用到的位运算
位1的个数	x = x & (x - 1)
2的幂	x = x & (x - 1)
颠倒二进制位	移位操作