在做 leetcode 时发现自己对二进制的相关知识不太了解，将自己所找资料进行总结。<!--more-->

#### 基础概念

##### 机器数

一个数在计算机中的二进制表示形式、叫做这个数的机器数。机器数带符号，最高位表示符号位，正数为 0，复数为 1.

###### 真值

由于第一位是符号位，所以机器数的形式值不等于真实的数值。为了区别起见，将带符号位的机器数对应的真正数值成为机器的真值。

例：0000 0001 的真值 = +000 0001 = +1，1000 0001 的真值 = –000 0001 = –1

##### 原码

原码就是在符号位上加上真正的绝对值，即第一位表示符号，其余为表示值。比如 8 位二进制：

> [正数 1]~原码~  = 0000 0001
>
> [负数 1]~原码~ = 1000 0001

则 8 位二进制数的取值范围就是：

> [1111 1111,0111 1111] 
>
> [-127,+127]

##### 反码

正数的反码是其本身

负数的反码是在原码基础上，符号位不变，其余各个位取反

> [+1] = [0000 0001]~原码~  = [0000 0001]~反码~
>
> [-1] = [1000 0001]~原码~ = [1111 1110]~反码~ 

##### 补码

正数的补码就是其本身

负数的补码在其原码的基础上，符号位不变，其余各位取反，最后 +1。【即在反码的基础上 +1】

> [+1] = [0000 0001]~原码~ = [0000 0001]~反码~ = [0000 0001]~补码~
>
> [-1] = [1000 0001]~原码~ = [1111 1110]~反码~ = [1111 1111]~补码~

#### 为什么要用原码、反码、补码

计算机有三种编码方式表示一个数，对于正数，三种编码格式的结果都是一样的

> [+1] = [0000 0001]~原码~ = [0000 0001]~反码~ = [0000 0001]~补码~

对于负数

> [-1] = [1000 0001]~原码~ = [1111 1110]~反码~ = [1111 1111]~补码~

可见，负数的原码、补码和反码都是不同的，原码是让人看的表示方式，为何会有反码和补码呢？

首先，人脑知道第一位是符号位，在计算的时候根据符号位，选择对真值区进行加减。但是对于计算机，加减乘除已经是最基本的运算，要设计的尽量简单，计算机辨别“符号位”显然会让计算机的基础电路变得十分复杂！于是人们想出了将符号位也参与运算的方法，根据运算法则，减去一个正数等于加上一个负数，所以机器可以只有加法而没有减法，这样计算机的设计就更简单了。于是人们探索将符号位参与运算，并且只保留加法的方法。

首先来看原码计算十进制的：`1-1=0`

> 1 - 1 = 1 + (-1) = [0000 0001]~原码~+[1000 0001]~原码~ = [1000 0010]~原码~ = 2~十进制~

用原码表示，让符号位也参与运算，结果是不对的。

为了解决原码做减法的问题，出现了反码

>  1 - 1 = 1 + (-1) = [0000 0001]~反码~+[1111 1110]~反码~ = [1111 1111]~反码~ = [1000 0000]~原码~ = -0~十进制~

结果貌似是对的，`-0`也是 0，但是`[0000 0000]~原码~`也表示 0，这样一来，0 会有两种编码表示。

于是补码出现了，解决了 0 的符号问题

>  1 - 1 = 1 + (-1) = [0000 0001]~补码~+[1111 1111]~补码~ = [0000 0000]~补码~ = [0000 0000]~原码~ = 0~十进制~

这样 0 可以用[0000 0000]~补码~ 唯一表示，而且可以用[1000 0000]~补码~来表示 -128，

在用补码运算的结果中，[1000 0000]补 就是 -128。但是注意因为实际上是使用以前的 -0 的补码来表示 -128, 所以 -128 并没有原码和反码表示.(对 -128 的补码表示[1000 0000]补算出来的原码是[0000 0000]原，这是不正确的)

使用了补码，不仅仅修复了 0 的符号以及存在两个编码的问题，而且还能够多表示一个最低数，这就是为什么 8 位二进制，使用原码或反码表示的范围为[-127, +127], 而使用补码表示的范围为[-128, 127]。

#### 原码、补码、反码再深入

计算机巧妙地把符号位参与运算，并且将减法变成了加法，背后蕴含了怎样的数学原理呢？

将钟表想象成是一个 1 位的 12 进制数。如果当前时间是 6 点，我希望将时间设置成 4 点，需要怎么做呢？我们可以：

> 1. 往后拨 2 个小时：6 - 2 = 4
>
> 2. 向前前拨 10 个小时：(6 + 10) mod 12 = 4
>
> 3. 向前拨 10+12=22 个小时：(6+22) mod 12 =4

2、3 方法中的 mod 是指取模操作，16 mod 12 =4 即用 16 除以 12 后的余数是 4。

所以钟表往后拨 (减法) 的结果可以用向前拨 (加法) 替代！

如何使用一个正数来"代替"负数呢？

##### 同余

> 两个整数 a、b，若他们除以整数 m 所得的余数相等，则称 a、b 对与模 m 同余
>
> 记作 a ≡ b (mod m)
>
> 读作 a 与 b 关于模 m 同余。

`mod`运算的数学定义

$$ x \quad mod \quad y \quad = \quad  x -y\lfloor x/y \rfloor $$ 

> -3 mod 2
>
> = -3 - 2*($\lfloor -3/2 \rfloor$)
>
> = -3 -2*2
>
> = 1

##### 开始证明

> 回拨 2 小时 = 前拨 10 小时
>
> 回拨 4 小时 = 前拨 8 小时
>
> 回拨 5 小时= 前拨 7 小时

结合上面学到的同余的概念。实际上：

> (-2) mod 12 = 10
>
> 10 mod 12 = 10
>
> (-4) mod 12 = 8
>
> 8 mod 12 = 8

-2 与 10 是同余的，-4 与 8 是同余的。

对于`mod`的线性运算定理

> 若 a ≡ b (mod m)，c ≡ d (mod m) 那么：
>
> (1)a ± c ≡ b ± d (mod m)
>
> (2)a * c ≡ b * d (mod m)

举个例子

> 7 ≡ 7 (mod 12)
>
> (-2) ≡ 10 (mod 12)
>
> 7 -2 ≡ 7 + 10 (mod 12)

现在我们为一个负数，找到了它的正数同余数。但是并不是 7-2 = 7+10, 而是 7 -2 ≡ 7 + 10 (mod 12) , 即计算结果的余数相等。

接下来回到二进制的问题上，看一下：2-1=1 的问题。

> 2-1=2+(-1) = [0000 0010]~原~ + [1000 0001]~原~= [0000 0010]~反~ + [1111 1110]~反~

先到这一步，-1 的反码表示是[1111 1110]。如果这里将[1111 1110]认为是原码，则[1111 1110]原 = -126, 这里将符号位除去，即认为是 126。

发现有如下规律：

> (-1) mod 127 = 126
>
> 126 mod 127 = 126

即有

> (-1) ≡ 126 (mod 127)
>
> 2-1 ≡ 2+126 (mod 127)

2-1 与 2+126 的余数结果是相同的！而这个余数，正式我们的期望的计算结果：2-1=1

所以说一个数的反码，实际上是这个数对于一个模的同余数，而这个模并不是我们的二进制，二十所能表示的最大值！这样就和钟表一样，转了一圈后总能找到在可表示范围内的一个正确数值。而 2+126 相当于钟表转过了一轮，因为符号位也是参与计算的，正好和溢出的最高位形成正确的运算结果。

既然反码可以将减法变成加法，那么现在计算机使用的补码呢？为什么在反码的基础上加 1, 还能得到正确的结果？

> 2-1=2+(-1) = [0000 0010]~原~ + [1000 0001]~原~ = [0000 0010]~补~ + [1111 1111]~补~

如果把[1111 1111]当成原码，去除符号位，则：

> [0111 1111]~原~ = 127

其实，在反码的基础上 +1, 只是相当于增加了模的值：

> (-1) mod 128 = 127
>
> 127 mod 128 = 127
>
> 2-1 ≡ 2+127 (mod 128)

此时，表盘相当于每 128 个刻度转一轮。所以用补码表示的运算结果最小值和最大值应该是[-128, 128]，但是由于 0 的特殊情况，没有办法表示 128, 所以补码的取值范围是[-128, 127]。