以通俗的方式理解位运算 （以位运算加法为例）

一. 必要知识

1. 位运算符运算法则:

与：1&1=1    其余情况结果为0
或：0|0=0    其余情况结果为1
非：~0 = 1    即:1换成0，0换成1
异或：1^1=0^0=0     1^0=0^1=1
进位：01<<1=10    01<<2=00      （数据位对齐后再运算）
退位：10>>1=01    10>>2=00      （数据位对齐后再运算）

2. 位运算的实质(个人理解)：

    对每一位运算后的记录。（位运算本身不影响其它位，得到的值只是对应每一位的结果）

3. 一些口头术语：

参考文章末尾，或注释。

二. 位运算的通俗理解

    在十进制加法运算中，因为我们的加法满足满十进一的规则，所以这种运算方式将会导致进位^[1]，从而导致了这样的一种结果：
    在十进制的四则运算^[2]里，每一位低位^[3]都可能因为四则运算而影响到下一位高位^[4]。

例子：
​ 9 + 1 = 10 #个位数影响了十位数
​ 99 + 1 = 100 #个位数影响了十位数和百位数

    而在我们的位运算中，以下4种位运算方式都没有进位规则。

例子：
​ 111 & 101 = 101
​ 101 | 110 = 111
​ 100 ^ 101 = 001
​ ~100 = 011

    此外，还要提到两种特殊的位运算进位和退位，看一下这两种情况下的运算结果：

在有限位数（这里为3 bit）下：
​ 100 >> 2 = 001
​ 111 << 1 = 110

    当然还有无限位数下运算，参考如下：

在无限位数下：
​ 100 >> 2 = 1
​ 100 >> 3 = 0
​ 100 << 2 = 10000

    看完这2种情况可能有人会说：这不是已经影响到了每一位上的数？甚至前后位还发生了“数据的丢失”！
    确切的说：不管是有限位数下还是无限位数下，进位和退位的运算都影响到了其它位。但特别要强调的是：位运算是“对每一位进行独立运算”，进位和退位也是如此：

    进位到头？则放弃最高位，最低位补0。（这是进位的规则）
    退位到头？则放弃最低位，最高位补0。（这是退位的规则）

    除此之外，其它的位的数并没有发生改变，对其的运算是纯粹的“移位”。
    正如把桌子上的苹果放到一旁的水果篮里，苹果本身是没有发生变化的，把它移到视野外也是如此，它只是不再你视野里罢了。
    不过视野之外的数据再也拿不回来了。

三. 以位运算做十进制加法为例理解

1. 预备运算知识

与：  可以确认该数位是否需要进位
异或：一种“无进位”加法
进位：完成进位

2. 加法原理
   在十进制中的加法1+1=2，1+9=10在二进制里表示为：

1+1=10（也就是2的二进制），1+1001=1010（也就是10的二进制）

2+6=8          2+3=5       15+15=30
10+110= 1000   10+11=101   1111+1111=11110

    通过尝试，我们可以发现二进制的加法和十进制的加法其实都有着共通的地方，也就是“满n进位”，即：满2进1，满10进1。我们列几个式子计算一下就清楚了：

加法运算竖式示例
    这便是二进制和十进制各自的2个数之间的加法运算了，然后我到底想解释什么呢？可能你已经发现这里的加法运算已经“低位影响高位”了。没错，但这是加法而并非是位运算。
    请注意上面列的竖式：待进位和结果位，我们如何通过位运算来得到这2个结果？

---

待进位的二进制计算可以观察到如下图表般的规律：

	1	0
1	1	0
0	0	0

而我们则发现这是一个与运算的规律。

结果位的二进制运算则有如下规律:

	1	0
1	0	1
0	1	0

我们发现这是一个异或运算的规律。

​   规律有了，那么我们开始开始尝试使用位运算完成加法计算：

一个数A，一个数B进行加法运算的步骤：

1. 计算A&B=C
2. 计算A^B=D
3. 我们需要进位，使用<<即进位运算符达成目的，即：C<<1 = E
4. ..

​   到步骤4时，问题来了。我们需要一些例子分析一下会有什么结果：

A = 0110, B=0111
A&B=0110
A^B=0001
110 << 1 = 1100

​   这里我们发现应该让1100和0001进行重复步骤的加算，因为1100和0001是2个全新的数，并没有让它们相加组合：

1100&0001=0000
1100^0001=1101
1100&0001结果为0，说明不需要进位,而且只有1个新的数，而这个数正是我们想要的结果：0110 + 0111 = 1101

​   回头完善步骤：

一个数A，一个数B进行加法运算的步骤：

1. 计算A&B=C
2. 计算A^B=D
3. 我们需要进位，使用<<即进位运算符达成目的，即：C<<1 = E
4. 如果C结果不为0，将新数D与新数E作为新的数A，数B按步骤1-3再次运算，直到得到A&B=0，此时A^B的值即可作为加法运算的结果。

​   至此，通过位运算完成加法计算已经说明完毕。我们可以发现位运算的作用真的就只是“在做标记”而已，是名副其实的“按位运算”。
   至于减法涉及到了一些特别的技巧，乘法除法其实按本文理解了位运算的本质后也并不会很难用位运算去实现它，所以就不再提及了，读者可以自行尝试，或者搜索其它作者的相关文章。

作者：sudaR(https://www.jianshu.com/u/71d294ca74c3)

---

本文所提及的口头术语的解释：

---

1. 即“满n进1”，如在十进制中：1+9 = 10，3+7 = 10 ↩

2. 即“加法、减法、乘法、除法”， 运算符号：+ - × ÷ ↩

3. 一种顺序上的描述，习惯上称右为低位。如十进制里的123，3相对与2为低位，2相对1为低位，3相对1为低位 ↩

4. 一种顺序上的描述，习惯上称左为高位。如十进制里的123，1相对与2为高位，2相对3为高位，1相对3为高位 ↩