二进制引发的思考
在做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]。