算法(一 原码,反码和,补码)

一, 机器数和真值

1. 机器数
   一个数在计算机中的二进制表示形式,叫做这个数的机器数. 用二进制数的最高位存放符号,正数为0,负数为1.
2. 真值
   将带符号位的机器数对应的真正数值称为机器数的真值.
   例：0000 0001的真值 = +000 0001 = +1，1000 0001的真值 = –000 0001 = –1

二, 原码,反码,补码

正数的反码和补码是其本身(原码)
[+1] = [00000001]原 = [00000001]反 = [00000001]补

负数的反码是在其原码的基础上, 符号位不变，其余各个位取反.
[-1] = [10000001]原 = [11111110]反

负数的补码是在其原码的基础上, 符号位不变, 其余各位取反, 最后+1. (即在反码的基础上+1)
[-1] = [10000001]原 = [11111110]反 = [11111111]补

为什么要使用反码和补码:

为了避免让计算机的基础电路设计变得十分复杂, 所以机器可以只有加法而没有减法, 根据运算法则减去一个正数等于加上一个负数, 即: 1-1 = 1 + (-1) = 0.

为了解决原码做减法的问题, 出现了反码:
1 - 1 = 1 + (-1) = [00000001]原 + [10000001]原 = [10000010]原 = -2(显然是错误的!)

使用反码: 1 - 1 = 1 + (-1) = [0000 0001]原 + [1000 0001]原= [0000 0001]反 + [1111 1110]反 = [1111 1111]反 = [1000 0000]原 = -0

但是会导致[0000 0000]原和[1000 0000]原两个编码(即+0和-0)表示0.

补码的出现就是为了解决+,-0的问题
1-1 = 1 + (-1) = [0000 0001]原 + [1000 0001]原 = [0000 0001]补 + [1111 1111]补 = [0000 0000]补 = [0000 0000]原

这样0用[0000 0000]原表示,而[1000 0000]原表示-128:
(-1) + (-127) = [1000 0001]原 + [1111 1111]原 = [1111 1111]补 + [1000 0001]补 = [1000 0000]补

[1000 0000]补实际上是使用以前的-0的补码来表示-128, 所以-128并没有原码和反码表示.(对-128的补码表示[1000 0000]补算出来的原码是[0000 0000]原, 这是不正确的)
[1000 0000]补 = [0111 1111]反 = [0000 0000]原 = 0 (错误)

[1000 0000]原 = [1111 1111]反 = [1000 0000]补

所以8位二进制, 使用原码或反码表示的范围为[-127, +127], 而使用补码表示的范围为[-2^8, 2^8-1][-128, 127] . 因为机器使用补码, 所以对于编程中常用到的32位int类型, 可以表示范围是: [-2^32, 2^31-1]

三, 原理

时钟回拨
将钟表想象成是一个1位的12进制数. 如果当前是8点,希望设置成6点:

1. 往回拨2个小时: 8 - 2 = 6
2. 往前拨10个小时: (8 + 10) mod 12 = 4
3. 往前拨10+12=22个小时: (8 + 22) mod 12 =4

负数取余
x mod y = x - y [x / y] (y != 0)

-3 mod 2 = -3 - 2 X [-3 / 2] = -3 - 2 X [-1.5] = -3 - 2 X (-2) = -3 + 4 = 1

回到上面的问题, -2与10是同余的.

(-2) mod 12 = 10

10 mod 12 = 10

要实现用正数替代负数, 只需要运用同余数的两个定理:

反身性:

a ≡ a (mod m) (同余数)

如果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)

接下来回到二进制的问题上, 看一下: 2-1=1的问题.
2-1=2+(-1) = [0000 0010]原 + [1000 0001]原 = [0000 0010]反+ [1111 1110]反 = [0000 0000]反

先到这一步, -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]