0.前言

这几天做到一些算法题，虽说用笨方法也可以做出来，但是强迫症看着执行用时那里怪难受的，于是翻来大佬的解题方法，于是发现了位运算的神奇用法。

在网上搜索了一下，本来想把这些用法直接注释在代码中，但是又觉得不方便查找，所以就先写在这里吧。

1.位运算概述

计算机中所有的数据都是以二进制存储的，计算机对二进制的运算（+,-,*,/）都是用的位运算。即先用位运算计算出二进制结果，再将结果转换为其他进制，比如十进制。

2.位运算符号

3.详细内容

1.与（&）

运算规则： 0&0=0 　0&1=0　 1&0=0 　 1&1=1

注意：负数按补码形式参与操作
用途：

• 清零：
  如果想将一个单元清零，即使其全部二进制位为0，只要与一个各位都为零的数值相与，结果为零。

• 取一个数的指定位：
  比如取数 X=1010 1110 的低4位，只需要另找一个数Y，令Y的低4位为1，其余位为0，即Y=0000 1111，然后将X与Y进行按位与运算（X&Y=0000 1110）即可得到X的指定位。

• 判断奇偶
  只要根据最未位是0还是1来决定，为0就是偶数，为1就是奇数。因此可以用if ((a & 1) == 0)代替if (a % 2 == 0)来判断a是不是偶数。

取余的更快操作：a % 2^{n == a & ( (2}n) - 1 )

2.或（|）

运算规则： 0|0=0 　 0|1=1 　 1|0=1 　 1|1=1

用途：

• 对数据的某位置1
  比如将数 X=1010 1110 的低4位设置为1，只需要另找一个数Y，令Y的低4位为1，其余位为0，即Y=0000 1111，然后将X与Y进行按位或运算（X|Y=1010 1111）即可得到。

3.异或（^）

运算规则： 0^{0=0 　 0}1=1 　 1^{0=1 　1}1=0

• 翻转指定位
  比如将数 X=1010 1110 的低4位进行翻转，只需要另找一个数Y，令Y的低4位为1，其余位为0，即Y=0000 1111，然后将X与Y进行异或运算（X^Y=1010 0001）即可得到。

• 与0相异或值不变
  例如：1010 1110 ^ 0000 0000 = 1010 1110

• 交换两个数

void Swap(int &a, int &b){
    if (a != b){
        a ^= b;
        b ^= a;
        a ^= b;
    }
}

4.取反（~）

运算规则：~0=1 　~1=0

用途：

• 使一个数的最低位为0
  使a的最低位为0，可以表示为：a & ~ 1。~1的值为 1111 1111 1111 1110，再按"与"运算，最低位一定为0。因为“ ~”运算符的优先级比算术运算符、关系运算符、逻辑运算符和其他运算符都高。

5.左移（<<）

运算规则： 将一个二进制位左移若干位，高位丢弃，低位补0

例如： a=1010 1011，a = a<< 2，a=1010 1100。

若左移时舍弃的高位不包含1，则每左移一位，相当于该数乘以2。

6.右移（>>）

运算规则： 将一个二进制位右移若干位，正数高位补0，负数高位补1，低位丢弃

例如：a=a>>2 将a的二进制位右移2位，左补0 或者 左补1得看被移数是正还是负。
操作数每右移一位，相当于该数除以2。

参考：https://www.cnblogs.com/yrjns/p/11246163.html