位运算包含&（按位与）、|（按位或）、^（按位异或）、<<（左移）、>>（右移）等二元运算符及~（取反）一元运算符。
假如把0和1比作两个开关的状态，两个开关同时控制一个小灯泡，小灯泡的状态不亮为0，亮为1就有：
| & | 0 | 1 |
|---|---|---|
| 0 | 0 | 0 |
| 1 | 0 | 1 |
即当两数二进制上的同一位都是1时，所得结果的这一位上才是1，否则都为0。相当于：
举例： 3 & 5 = 1
| 3 | 0 | 1 | 1 |
|---|---|---|---|
| 5 | 1 | 0 | 1 |
| 1 | 0 | 0 | 1 |
| | | 0 | 1 |
|---|---|---|
| 0 | 0 | 1 |
| 1 | 1 | 1 |
即当两数二进制上的同一位都是0时，所得结果的这一位上才是0，否则都为1。相当于：
举例： 3 | 5 = 7
| 3 | 0 | 1 | 1 |
|---|---|---|---|
| 5 | 1 | 0 | 1 |
| 7 | 1 | 1 | 1 |
| ^ | 0 | 1 |
|---|---|---|
| 0 | 0 | 1 |
| 1 | 1 | 0 |
即当两数二进制上的同一位相同时，所得结果的这一位上是0，不同则为1。相当于：
举例： 3 ^ 5 = 6
| 3 | 0 | 1 | 1 |
|---|---|---|---|
| 5 | 1 | 0 | 1 |
| 6 | 1 | 1 | 0 |
以上是三个类似逻辑运算符的位运算符，下面看看移位运算符。
<<（左移）1 << 2 就是在1的二进制数码的后面添上2个0，即：
1(D) << 2(D) = 1(B) << 2(D) = 100(B) = 4(D)
x << y 其实就是x乘以2y，如 2 << 3 = 16。
>>（右移）10 >> 2 就是划去10的二进制数码的最低2位，即：
10(D) >> 2(D) = 1010(B) >> 2(D) = 10
10(B) = 2(D)
x >> y 其实就是x整除2y，如 24 >> 3 = 3。
最后看看一个一元运算符。
~（取反）不是题外话的题外话：
补码（我们采用8位二进制数码进行示范）对于正数，其补码就是其原来的二进制数码，如5的补码是00000101。
对于负数，其补码是其去掉负号后数字的二进制数码中每位0变1，1变0后再给其二进制数码加1（不管符号位，其实可以去掉符号位当正数操作），如-5的补码是11111011（5的二进制数码00000101 -> 11111010 -> 11111011）。
x的反码就是将x的补码中每一位0变1，1变0，得到的数码。
如4的反码是11111011，-5的反码是00000100。
对x取反得到y，则x的反码与y的补码相同。
如：~0 = -1， ~-5 = 4。
x & y = y & x
x | y = y | x
x ^ y = y ^ x
| x & x | x | x | x ^ x |
|---|---|---|
| x | x | 0 |
由 一 可得一个数按位异或自己得到0。在“缺失的数字”等题中，异或就可以派上用场。x ^= y; y ^= x; x ^= y;也可以起到数字交换的作用。Nim游戏中每堆石子数量的异或值也可以用来判断当前先手的状态。这里简单介绍一下。
缺失的两个数字给定1到N中N - 2个不重复的数字，问缺失了哪两个。
若只缺一个数字，则只需初始化一个整型变量x = 0，让x与1到N中数字都按位异或一遍，再让x与给定的数字一一按位异或，最后的x即为缺失的数字。
那么对于消失的两个数字，先进行一遍上述操作，最后得到的x就是缺失的两个数字的异或值，
这样x上为1的位对应的两个数字中这一位一个是0而另一个是1。接下来任意选取x上为1的一位，这位上为1的数字就有：
- 1到N中这位上为一的数字；
- 给定的数字中这位上为一的数字；
- 缺失的其中一个数字；
我们发现把上述中的两项中的元素（可以通过将这里面的元素按位与x然后判断选中的那位是否为1来判定是否符合条件）异或一下，就可以得到缺失的其中一个数字，此时将x异或这个数字就可以得到另一个数字。
Nim的必胜态与必败态共N堆石子，第i堆有Xi个（i = 1, 2, …, N）。
必胜态：X1 ^ X2 ^ … ^ XN != 0
必败态：X1 ^ X2 ^ … ^ XN == 0
至于原理，这里不做赘述。
位运算因其操作在二进制位上进行，所以速度比普通运算快。
下面给出常见的效果相同的运算对照表。(我能想到的就那么几个)
| x % 2 | (int)x / 2 | -x | tmp = x; x = y; y = tmp | x是否为2的幂 |
|---|---|---|---|---|
| x & 1 | x >> 1 | ~x + 1 | x ^= y; y ^= x; x ^= y | x & (x - 1) == 0 |
当然不能因为位运算速度较快就强行用位运算，具体问题具体分析，代码的可读性也是至关重要的。
四.常见用途 求一个数二进制上为1的最低位在树状数组中，我们通常需要求一个数二进制上为1的最低位（太长了但不知道怎么说清楚）这里利用到 1 + ~x = -x 这个性质可以得到 x & -x 即为 x & (1 + ~x) 而取反会使x二进制位上0变1，1变0。这样一来，x最低几个0都会变成1，而我们要求的那位会变成0，此时给~x加上1（即成了-x），让那几位全部进位，一直进到我们要求的那位，此时所求位以下皆为0，以上的数码两数皆不同，故x & -x就会得到我们想要求的x二进制上为1的最低位。（如24：00011000B & 11101000B = 1000B）
int LowestBit(int x) {
return x & -x;
}
leetcode 371.
（其实直接return a + b;也可以）问题很简单，用位运算计算两数之和。我们回顾一下&和^的运算法则[假装思考]。按位与只有在两数同一位都为1时所得结果的这一位上才为1，而当满足这种情况时需要进位，所以两数二进制相加的进位值就是a & b << 1；相反地，按位异或在两数同一位都为1时所得结果的这一位上为0（没有进位），则可知按位异或恰恰是不进位的加法（得到不进位加法的结果为a ^ b）。所以只要将进位值与不进位加法的结果按照同样的方法相加直至不再产生进位即可。（不过注意如果有负数则需在左移时进行强制类型转换成无符号整型）
int getSum(int a, int b) {
if(b == 0) return a;
return getSum(a ^ b, (unsigned int)(a & b) << 1);
//递归求不进位加法的结果与进位值的和
}
未完待续
感谢阅读与支持，如有言之不慎之处，请多指教[微笑]！！！
