# 0. 概要
前两篇文章我们了解了二进制的基本原理（[谈谈二进制（一）](http://www.dubingxuan.com/article/6/)）以及二进制的四则运算（[谈谈二进制（二）](http://www.dubingxuan.com/article/8/)），本篇我们一起来看看二进制的位运算。
先来看一下有哪些位运算：
上表中列出了我们编程语言中的所有位运算符以及它们对应的规则。在前面的文章中我们讲过，二进制的`1`和`0`对应了电子元器件中的高低电平，或是开和关，而实际上，`1`和`0`也可以代表逻辑中的`真`与`假`。因此，上表中的前三个运算符其实也是逻辑运算符，而它们在逻辑运算中的规则，和二进制位运算基本一致，我们会在文中提及时做一些说明。
# 1. 位运算
所谓位运算，指的是直接对二进制的位进行的运算，它只针对二进制的每一个位，所以它与前面我们讲的四则运算的最根本的区别是：**位运算没有进位**。
注意了，本篇文章所谈的位运算，都是针对二进制的运算，虽然我们可以将这些运算符直接作用在十进制数上（代码中），但它背后的计算过程却是针对该数对应的二进制数的。
我们一个一个来看。
# 1.1 与
与运算，运算符号是`&`。首先，与运算是一个二元运算，什么意思呢？就是像我们的加减乘除四则运算一样，与运算也需要两个数进行运算，然后生成第三个数，譬如：`A & B = C`。
与运算的规则正如上面表格中所说，**参与运算的两个数的每个对应位上的数，如果都为`1`，则结果也为`1`，否则为`0`**。解释一下，假如我们有两个只有一位的最简单的二进制数，那么它们之间进行与运算的结果只有如下三种：`1 & 1 = 1`，`1 & 0 = 0`，`0 & 0 = 0`。嗯，至少在这组运算中，看上去是不是很像乘法？实际上前面我们也说到了，位运算表格中的前三个运算符也是逻辑运算符，这里我们把`1`看做`真`，`0`看做`假`，则这三个运算结果就变成了逻辑运算的结果，`&`所代表的`与`，其实就是`且`。`真且真`，其结果才能为真，否则都为假，也就是`0`了。
上面说的是一位二进制的运算情况，也顺带提了一下逻辑运算，那么多位的二进制数之间的与运算又是怎样的呢？其实就是把两个数的每一位都与对方做一个与运算，最后把结果按位排列起来就行了，竖式如下：
上面两个数分别对应十进制的`5`和`7`，我们可以用代码去验证一下：
```python
print(5&7) # 5
```
这就是二进制的与运算，是不是非常简单？其实早在前面讲四则运算的时候我们就已经发现，二进制的运算真的非常简单，而今天我们看到的位运算，甚至连进位都省了，真的是……简单。
# 1.2 或
紧接着，或运算，运算符为`|`，同样是二元运算。它和上面的与运算的运算方式一致，也是两个数的每一位与对方的对应为进行运算，运算规则唯一不同的地方就是，**或运算只需要其中一个数为`1`，结果就为`1`**。即两个一位二进制数之间的或运算的结果有如下三种：`1 | 1 = 1`，`1 | 0 = 1`，`0 | 0 = 0`。同样的，或运算也是一种逻辑运算，这里就不再展开了，我们直接来看例子，还是`5`和`7`：
结果是`7`，我们同样用代码去验证一下：
```python
print(5|7) # 7
```
非常简单。
# 1.3 异或
异或运算，运算符为`^`，也是一个二元运算，运算方式同前面两个运算一样，规则方面：**对应位的两个数`不同`时为`1`，否则为`0`**。它的运算规则一部分和或运算类似，只要两个数中有一个是`1`，结果就可以是`1`，但必须是相异的两个数。这大概就是它`异或`这个名字的来源。
依然是`5`和`7`，我们来看一下结果：
结果是`10`，也就是`2`，验证一下：
```python
print(5^7) # 2
```
记得，异或就是不相同时为`1`，相等为`0`，也就是判断两个对应数字是否`不相等`。同时，异或也是一个逻辑运算符，运算规则同理。
# 1.4 取反
取反运算，符号为`~`。这个运算就稍微有点特殊了，首先，它是一种一元运算，也就是它只对一个数进行位运算，然后形成结果；其次，取反运算还涉及到了补码、反码、原码之类的问题。
我们先来看它的规则：**二进制每一位数取反，即`0`变`1`，`1`变`0`**。看上去非常简单对吧？我们来按照我们初步理解的规则试一下：
***（注意，上面这个答案是错误的。）***
我们对`101（5）`取反得到了`010`也就是`2`，然后用代码验证一下：
```python
print(~5) # -6
```
结果是`-6`！好奇怪，我们再用`C++`试一下：
```c++
#include "iostream"
int main(int argc, char** argv) {
int number;
number = 5;
std::cout << ~number;
return 0;
}
// -6
```
结果依然是`-6`！
正如前面所说，按位取反运算涉及到了补码之类的骚操作，而这些内容不在本篇文章的涉及范围内，将会在下一篇二进制文章中讲解，因此这里不做详细展开，只大概解释一下：
上面我们用到的`int`型的整数都是有符号数，而计算机在存储有符号数时均使用`二进制补码`，而补码这个东西，简单说会在高位（数字自身的二进制范围以外）表示数字的正负，其中`0`表示正，`1`表示负，因此我们在做按位取反操作后，原数字不仅仅是自身按位取反，高位上的我们看不见的部分也取反了，所以`5`变成`-6`，就是从正数变成了负数。那为什么是`-6（-110）`呢？这个就涉及到负数补码的运算过程了，等我们下一篇讲到的时候再提。
总之我们记住，按位取反的结果就是**原数取负值后再减一**。譬如上面的`5`变成`-6`，就是`5 × (-1) - 1 = -6`，同样的，我们如果对`-6`取反，会得到`-6 × (-1) - 1 = 5`。
以上就是按位取反，细心的朋友可能注意到了，这里其实还有个小问题，上面提到的按位取反变成负数，是因为补码，而补码的高位会用`1`和`0`表示正负，那么如果对一个无符号整型做取反呢？我们来试验一下：
```c++
#include "iostream"
using namespace std;
int main(int argc, char** argv) {
unsigned int five;
five = 5;
cout << ~five;
return 0;
}
// 4294967290
```
对于一个无符号数`5`取反后得到了`4294967290`，看上去有点像溢出了，但实际上，`4294967290`这个数等于\\(2^{32}-6\\)，这两个数，用`32`位二进制数表示，分别是这样的：
```
0000,0000,0000,0000,0000,0000,0000,0101 // 5
1111,1111,1111,1111,1111,1111,1111,1010 // 4294967290
```
整个`32`位都对上了，这回是真·按位取反了。这是无符号数的特殊性，却更符合我们的直觉。而\\(2^{32}-6\\)中的这个`-6`很凑巧，正好是有符号数`5`的取反结果。
## 1.5 左移
好了，最麻烦的一个运算讲完了，接下来是两个互为逆运算的运算，先来看看左移运算。
左移运算，符号为`<<`，是一个二元运算。运算规则是，**二进制所有位全部左移若干位，若高位溢出，则丢弃，低位补`0`**。很多人第一次看到这个运算的时候会很懵，不知道它到底要干嘛，什么叫左移若干位？其实它的运算规则也很简单，我们举一个例子来看，还是`101（5）`好了，我们来计算一下`101 << 1`的结果，这个式子的意思是，`101`这个数左移`1`位。
我们注意观察`1010`这个结果，看上去是不是就像，在`101`的后面（右边）加了一个`0`？嗯，没错，这个直觉是对的，`101 << 1`就是在`101`的后面加了一个`0`。那为什么叫左移呢？我们来把上面的竖式稍稍做一些改动：
我们在`101`的右边加了一个基准线，然后当我们做`101 << 1`时，以这根线为准，整个`101`**向左**移动了`1`位，最后在`101`和基准线之间添加一个`0`，得到了`1010`这个结果。这就是**左移**的原因了，虽然看起来像是在原数的右边加了`0`，其实是**整个数字以一根看不见的线为基准，向左移动了`n`位**。因为右边是低位，所以低位补`0`，而高位如果超过了表示范围，发生了溢出，就直接丢弃。
解释完了运算规则，我们再来看看`101 << 1`的结果`1010`，这个数字的十进制是`10`，正好是`101（5）`的`2`倍，那如果我们继续左移呢？也就是`101 << 2 = 1010 << 1 = 10100`，这个`10100（20）`又是`10`的`2`倍，`5`的`4`倍。
```python
print(5<<1) # 10
print(5<<2) # 20
```
看来我们发现了一个规律：**二进制每左移运算一位，则结果是原来的`2`倍**。所以如果左移`n`位，得到的结果就是原来的\\(2^n\\)倍。
这是个很显而易见的规律，但许多人在刚接触左移，二进制的时候，不是很理解，为什么是`2`的倍数？因为……这是二进制，嗯，就么简单。好吧，我再举一个例子，相信不懂的朋友们看了这个例子就明白了。
我这里创造一个运算符`<-`（我不知道实际上有没有这样的运算符），假设它的作用和`<<`一样，也是左移，但作用于`十进制`数字，运算规则和`<<`一模一样。接着我们来计算`5 <- 1`，按照左移运算的规则，`5`向左移动一位，低位补`0`，结果就是`50`。看到了吗？这个结果是`5`的`10`倍！也就是我们平时常说的，在什么什么数字后面加个`0`。十进制，所以倍数是`10`，二进制，所以倍数是`2`，这一点相信看过我前面文章**【[谈谈二进制（一）](http://www.dubingxuan.com/article/6/)】**的朋友们一定不会陌生。同理，如果在八进制数后面添一个`0`，结果会是原数的`8`倍，十六进制就是`16`倍。
左移运算其实帮我们又进一步地理解了进制。
## 1.6 右移
说完了左移，接着是右移。右移是左移的逆运算，也就是原数右边（和上面左移相同位置）以一根线为基准，整体**向右**移动`n`位，低位，也就是移动到基准线右边的数字则被丢弃。
譬如`101 >> 1 = 10`，所以`5 >> 1 = 2`。我们知道，整数的除法计算时会舍去小数部分，因此`5 / 2 = 2`，则右移是除以\\(2^n\\)这个规则也成立。
# 2. 位运算的应用
## 2.1 代码库中的应用
很多人觉得二进制位运算这个东西学了没用，因为平时写代码也用不到。但实际上，二进制位运算在一些代码库中非常常见，它常被用于设置一些标识（`flag`），做一些定制化的设置工作。举几个例子，最近在用做`Go`语言做项目，`Go`语言标准库中的`log`和文件打开操作都用到了二进制的位运算：
```go
package main
import (
"log"
"os"
)
func main() {
f, _ := os.OpenFile("filename", os.O_WRONLY|os.O_CREATE, 0666)
defer f.Close()
log.SetFlags(log.Ldate|log.Lshortfile)
}
```
它们的用法一致，都是用或运算来设置标志位。除标准库外，很多第三方库也用到了二进制的位运算，譬如`Go`语言的一个用来做定时任务的第三方库`cron`（[https://github.com/robfig/cron](https://github.com/robfig/cron)）中用来解析`Crontab`表达式的部分，就用到了和上面标准库中类似的方法。具体细节就不展开讲了，大家有兴趣的可以去看一下它们的源码。
## 2.2 算法应用
上面说的几个都是在代码库中的应用，因为涉及源码细节比较多，限于篇幅没有展开。这里介绍一个实际的算法例子，来看一下二进制的位运算在解决实际问题时的具体细节。
`leetcode`第`287`题**Find the Duplicate Number（寻找重复数）**，这题有很多种解法，其中就可以使用二进制的位运算来设置标志位，从而解决问题。我先把原问题的中文版题目贴上来：
```
给定一个包含 n + 1 个整数的数组 nums，其数字都在 1 到 n 之间（包括 1 和 n），可知至少存在一个重复的整数。假设只有一个重复的整数，找出这个重复的数。
示例 1:
输入: [1,3,4,2,2]
输出: 2
示例 2:
输入: [3,1,3,4,2]
输出: 3
说明：
1. 不能更改原数组（假设数组是只读的）。
2. 只能使用额外的 O(1) 的空间。
3. 时间复杂度小于 O(n2) 。
4. 数组中只有一个重复的数字，但它可能不止重复出现一次。
来源：力扣（LeetCode）
中文链接：https://leetcode-cn.com/problems/find-the-duplicate-number
英文链接：https://leetcode.com/problems/find-the-duplicate-number/
```
然后是代码：
```python3
class Solution:
def findDuplicate(self, nums: List[int]) -> int:
"""
:type nums: List[int]
:rtype: int
"""
base = 0
for i in nums:
if base == base | (1 << i):
return i
base |= (1 << i)
```
我直接把`leetcode`上提交的代码拿上来了，所以保留着`leetcode`上的格式。在解析这段代码之前，有些情况我要先说明一下，其实这段代码并没有完全符合题干中的要求，题干`说明2.`要求我们只能使用额外`O(1)`的空间，但上面的代码其实使用了`O(n)`的空间，因为`for`循环中每一次循环都计算产生了一个`1 << i`。当然，这段代码可以通过`leetcode`，而且这个小问题并不影响我们今天的主题，二进制位运算，所以可以暂时忽略它。大家也可以想一想，有没有什么办法可以改造一下这段代码，让它只使用`O(1)`的空间呢？
我们来看代码，首先，我们设一个基准值`base = 0`，然后开始遍历传入的数字列表`nums`，接着是一个判断语句，它很重要，但我们先略过它，来看代码的最后一句`base |= (1 << i)`。这句什么意思呢？我们拆解一下来看。
**它是让`base`与另一个数进行`或运算`得到一个新的`base`**，而`base`或运算的对象是`1 << i`，我们知道，`i`是`num`中循环的元素，所以`1 << i`得到的二进制结果会是一个`1`加上`i个0`，譬如`1 << 3`，结果就是`1000（3个0）`。这种后面全`0`的二进制数，其实就是在告诉我们它的**位置**，`1000`就是说当前循环到的`3`这个值，它的位置在第三位（右边低位数起）。
我们将这个左移运算后的结果与`base`相或后，得到一个新的值，因为`base`一开始是`0`，按照或运算的规则，`0`与任何数相或，都是那个数自己。所以，结合上面解析的左移运算结果的意义，这个或运算的目的，是`nums`列表中的元素在**占位**，先来先到：**如果我前面没有跟我一样的元素，则我就占到了属于我的位置上**。那如果前面已经有了呢？那么**它在位移运算后再与`base`相或，得到的值依然是`base`的原值**，也就达到了刚才被我们略过的那句判断`if base == base | (1 << i)`的触发条件，也就找到了那个重复的数。
为什么呢？这依然是或运算的规则导致的，`1 | 1 = 1`，刚才我们说到，`1 << i`的意义是声明位置，属于我的位置就是`1`，如果前面有了一个和我相同的元素，则那个位置在我来之前就被占而置为`1`了。这时，我如果再和`base`进行或运算，那个属于我的位置在运算后还是`1`，`base`没有任何改变，因此`if`语句的条件就成立了。
譬如一个列表`[3, 1, 3]`，第一个数是`3（1 << 3 = 1000）`，第一次`if`判断为`False`，`base`自或运算，得到`base = 1000`；
第二轮是`1（1 << 1 = 0010）`，与`base`或运算后为`1010`，不等于`base`的当前值`1000`，判断为假，计算后赋值`base = 1010`；
第三轮是`3（1 << 3 = 1000）`，与`base`或运算后得到`1010 | 1000 = 1010`，而`base`的原值也是`1010`，于是`if`语句被触发，我们找到了这个重复的值`3`。
这就是这一题二进制位运算解法的详尽算法思路，其实在我们理解了位运算后，这种思路很容易就能理解，它的核心就是一个`占位`。有了这种思维后，我们再去看`2.1`章节中提及的那些代码库的二进制算法，相信也会容易了很多。
结尾之前，这里要再提一个东西。上面这段代码，其实有一个看上去像`BUG`的地方：**如果`base`的或运算对象是`0`呢？那不就也等于自身了吗？**嗯，首先，题目中给的数字是`1到n之间`，所以一定是正整数，那么`1 << i`的结果就不可能为`0`。实际上，即使`i`为`0`，这个结果也不可能为`0`，而是`1`。按照位移运算的规则，只有`1`右移运算后，结果才能为`0`。那如果左移**负数**个单位呢？很遗憾，左移不支持负值，会报错：
```python
print(1 << -1)
# ValueError: negative shift count
```
# 3. 结尾
这一篇文章我们了解了二进制的按位运算，并且用一个`leetcode`原题的例子讲解了二进制位运算的应用。在下一篇，我们就要进入让很多初学二进制的人们非常头疼的补码、反码之类的世界了。