原码、反码、补码、移码

原码

最高位是符号位 (0正1负), 其余位表示数值的绝对值.

规则:最高位是符号位 (0正1负), 其余位表示数值的绝对值.
举例:+5 = 0000 0101, -5 = 1000 0101.
优缺点:简单易懂, 比大小方便, 但加减运算复杂 (符号位不能直接参与运算), 且存在"正负零" (0000 0000 和 1000 0000 都表示0), 导致浪费.

反码

反码是历史长河中原码到补码的过渡产物.

原码的弊端

前面说了, 原码的符号位无法直接参与计算, 举个例子:
原码表示:

1 2	+3 = 0011 -3 = 1011

问题来了:如果直接做二进制加法:

  0011 (+3)
+ 1011 (-3)
------
  1110

结果不是 0000.
也就是说:
原码虽然很好理解, 但不适合直接拿来做加法.

反码的出现

正数的反码不变: +3 = 0011
负数则把原码的 数值部分 全部取反: -3 原码 = 1011, -3 反码 = 1100
和原码一样, 0 有两个 1111 (负零) 和 0000 (正零)

于是:

  0011  (+3)
+ 1100  (-3)
------
  1111

虽然还是不是 0000, 但已经非常接近了.
1111 在反码体系里表示 -0.
所以反码解决了一个重要问题:

+3 + (-3)
= 0011 + 1100
= 1111
= -0

但是它没解决原码里 0 有两个的问题:
反码存在两个 0.

补码

补码的数学来源

补码诞生之前, "补数"的数学思想在机械计算器和计算机出现之前就已经存在, 所以, 不存在某一天某一个人突然发明了二进制补码.

我们先看十进制 (只有两位):

25 - 17 正常做法:

 25
-17
---
  8

但是如果机器只有加法器, 就需要把 25 - 17 变成: 25 + 某个东西, 最后得到 8.
于是 25 - 17 + 100 = 108 变成 25 + 83 = 108
由于我们只有两位, 于是:25 + 83 = 108

这个 83 就是 17 的补数

此时我们再来看补码. 其实就是为了减法而出现的二进制补数, 而前面的 1 也正好充当了符号位.

这种通过溢出来得到结果的方式, 还有一个名字叫模运算, 也就是除法得到余数.
$(25 + 83) \% 100 = 8$

补码的特点

补码是 $2^n+x$

n 是当前数的位数, 对于 4 位就是 10000

例如我们求 $-5$ 的 4 位二进制补码, 真值是 $-0101$

10000
-0101
-----
 1011

二进制减法的规律

二进制减法算起来别扭, 咱们可以从十进制推一下规律

10000-327=673 这口算都能算, 因为之前前几位加起来等于 9, 最后一位加起来等于 10 就行
10000-460=540 这也能口算, 因为我们可以忽略最后的 0, 倒数第二位加起来等于 10, 前几位加起来等于 9

为什么要这样？因为 9 差 1 进位, 所以只要最后能进位, 前几位就会像多米诺骨牌一样全部进位

换到二进制, 我们直接上难度:

1 0000 0000 - 0010 1101=?
按照之前的规律, 前面的相加差1进位, 最后一位加起来直接进位
那就是 1101 0011

如果感兴趣, 还可以试着计算任意二进制减法, 是差不多的规律

值得一说的是: 补码是现代计算机底层真正存储和运算整数的方式.

补码的计算 (负数)

补码的计算有别于其他码, 要先判断有没有, 或者说, 能否用补码表示.
以 8 位二进制举例, 负数里只有 -1 ~ -128 能用补码表示.

真值, 绝对值按位取反再 +1
按补数理论, 按位取反再 +1 正好算得补数
原码, 符号位不变数值按位取反再 +1
因为负数原码的符号位是 1 , 因此只用将数值按位取反
反码, 符号位不变, 直接 +1
因为反码就是原码的符号为不变, 数值按位取反

+1会进位顶掉符号位吗?

在大部分的计算中, 原码变补码和反码变补码并不会因 +1 而顶掉符号位, 除非原来是 $-0$
比如: 原码 $1000 0000$ 符号不变, 按位取反 $1111 1111$ +1 后变为 $0000 0000$ 这在补码中是正零
而原码的正零 $0000 0000$ 因为符号为正, 所以补码就是 $0000 0000$

按位取反的意义

对应前面提到的十进制减法, 二进制的按位取反, 恰好就是让两个数差 1 进位

为啥10000000被定义为-128

1000 0000 被定义为 -128 并不是强行定义
从 0 开始算的前 128 个数 (0 ~ 127), 首位是 0, 充当正数
后 128 个数, 首位是 1, 充当负数 (-128 ~ -1) (负数的补码越大, 说明负数越小)
在上限是 256 的情况下, 为了让 -128 的能被补码表示, 所以 128 的补数就规定为 -128

一个补码的首位有负权值的含义, 例如:
$1000 0000\to -2^7+0+0+\cdots+0=-128$
$1001 0111\to -2^7+2^4+2^2+2^1+2^0=-105$

一个 8 位的二进制数, 有 1 个 0, 127 个正数, 128 个负数

补码的优势

零唯一:0000 0000 表示 0, 不存在负零, 1000 0000 被规定为 -128 (多表示一个最小负数).
减法变加法:符号位可直接参与运算, 5 + (-5) 直接相加得 0000 0000, 无需特殊处理, 极大简化了CPU设计.
符号位双重含义, 补码的首位可看作符号位, 也可直接作为负权值参与运算.

移码

什么是移码

移码 = 真值 + 偏置值

二进制有 n+1 位, 数值位是 n 位, 移码就是将所有数都增加偏置值, 让负数变成正数, 来解决负数不好比较的问题, 比如偏置值是128:

真值	移码	移码 (二进制)
-5	123	0111 1011
-4	124	0111 1100
-3	125	0111 1101
-2	126	0111 1110
-1	127	0111 1111
0	128	1000 0000
+1	129	1000 0001
+2	130	1000 0010
+3	131	1000 0011
+4	132	1000 0100
+5	133	1000 0101

此种情况, 8 位移码的表示范围是 -128 ~ 127

浮点数存储

移码最常见的应用就是浮点数存储, IEEE 754 对正规数的指数采用偏置表示, 单精度的偏置值为 127.
指数域全 0 和全 1 还被保留用于表示特殊值.

浮点数的来源是科学计数法

$12300000 = 1.23 \times 10^7$ 的小数点从最后面移动到 1 后面.

$0.00000123 = 1.23 \times 10^{-6}$ 的小数点从前面移动到了后面.

浮点数的含义是指的是小数点可以移动
IEEE 754 里, 32 位 float 里:符号位 1 位, 阶码 8 位, 尾数 23 位.
对于二进制正规化浮点数, 首位一定是 1, 所以可以省略, 其实有效数字是 24 位, 1 被省略了.

其中阶码用移码, 尾数的有效数部分采用隐含最高位 1 的规格化表示 (也就是原码去除符号位)

移码的计算

采用 IEEE 754 标准, 移码偏置值是 $2^{n-1}-1$ (n是移码位数), 也就是 127

$-1.1011\times2^{-5}$

符号位是 1 代表负号
阶数是 $127-5=122$ 转为 8 位二进制是 01111010
尾数是 1.1011 去除首位 1 后的小数, 后面补 0, 结果如下:

1 01111010 10110000000000000000000

可以观察到, 移码和补码很类似,

补码是将负数加一个值让负数大于正数
补码是所有数都加一个值, 让正数还在前面, 但负数变为正数

所以补码和移码是镜像, 我们做个表格对比下:

真值	补码	移码(Bias=128)
-128	1000 0000	0000 0000
-127	1000 0001	0000 0001
…	…	…
-1	1111 1111	0111 1111
0	0000 0000	1000 0000
1	0000 0001	1000 0001
…	…	…
127	0111 1111	1111 1111

可以看到补码和移码只有一个符号差别, 但前提是:

位数一致
移码的偏置值是 $2^{n-1}$

为什么, 因为移码 = $x+2^{n-1}$ , 补码是 $x+2^n$ , 二者差了 $2^{n-1}$

补充

变形补码(模四补码)

\begin{aligned} &\text{默认 变形补码一共 n 位, 其中前两位是符号位}\\\\ &[x]_{\text{变补}}= \begin{cases} 00,x, &0\le x<2^{n-2}\\ 2^{n}+x=2^{n}-|x|, & -2^{n-2}\le x<0 \end{cases} \pmod{2^n} \end{aligned}

可以简单理解为, 变形补码就是将普通的补码增加了一个符号位

常规的补码, 又被成为模二补码, 也就是基于二进制的补码 $mod(2^n)$
模四补码, 也就是基于四进制的补码, 也就是用二进制表示的模四补码 $mod(4^{\frac{n}{2}})=mod(2^n)$ 其实一样
(二进制, 四进制, 八进制, 十六进制. $2^n$ 进制可以相互表示)

符号位	意义
00	正数
11	负数
01	正溢出
10	负溢出

变形补码溢出

// 正溢出
 00 101 (+5)
+00 110 (+6)
-------
 01 011 (+11)

// 负溢出
 11 001 (-7)
+11 001 (-7)
-------
 10 010 (-14)

因为两个数进行加减法, 结果肯定最多进位 1 位, 所以对于补码, 变形补码就增加了一位来推断结果是如何溢出的