二进制引发的思考
在做 leetcode 时发现自己对二进制的相关知识不太了解，将自己所找资料进行总结。
基础概念
机器数
一个数在计算机中的二进制表示形式、叫做这个数的机器数。机器数带符号，最高位表示符号位，正数为 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 点，需要怎么做呢？我们可以：
往后拨 2 个小时：6 - 2 = 4
向前前拨 10 个小时：(6 + 10) mod 12 = 4
向前拨 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]。