算法：常见位运算技巧总结
基础位运算
按位与 & ：有0为0，无0为1
按位或 | ：有1为1，无1为0
按位异或 ^ ：相同为1，不同为0
按位取反 ~ ：0变成1,1变成0
左移 << : 二进制序列向左移
右移 >> ：二进制序列向右移
一、判断一个数n的二进制表示中的第x位是0还是1
(n >> x) & 1
n >> x 将n的第x位放到最右边第0位
与1 按位与（1的二进制序列为000000…… 1）
即可判断第x位是0还是1
二、将一个数n的二进制表示中的第x位变成1
n |= (1 << x)
要将第x位变成1，需要第x位按位或1
1 << x 造出了第x位为1，其他位为0的二进制序列
三、将一个数n的二进制表示中的第x位变成0
n &= ~(1 << x)
要将第x位变成0，需要第x位按位与0
1 << x 造出了第x位为1，其他位为0的二进制序列
对该序列取反，就早出了第x位为0，其他位为1的二进制序列
四、提取一个数n的二进制表示中的最右边的1
n & (-n)
-n 的本质是将一个二进制数最右边的1的左边区域全部变成相反的数
-n = ~n + 1
eg
n = 11010001010101100000
-n = 00101110101010011111 + 1
= 00101110101010100000
五、干掉一个数n的二进制表示中的最右边的1（变成0）
n & (n - 1)
n - 1 的本质是将一个二进制数的最右边的1的右边区域（包括自己）全部取反
eg
n = 11010001010101100000
n - 1 = 11010001010101011111
六、按位异或(^) 运算律
a ^ a = 0
a ^ 0 = a
a ^ b ^ c = a ^ c ^ b