0%

关于机器数的一些知识

Posted on Edited on In

基础概念

机器数与真值

机器数（computer number）是将符号”数字化”的数，是数字在计算机中的二进制表示形式。机器数有2个特点：一是符号数字化，在计算机用一个数的最高位存放符号, 正数为0, 负数为1；二是其数的大小受机器字长的限制。比如在字长 8bit 的计算机中，+8 机器数就是 00001000，而 -8 的机器数则是 10001000。

不带符号的数是数的绝对值，在绝对值前加上表示正负的符号就成了符号数。直接用正号 “+” 和负号 “-” 来表示其正负的二进制数叫做符号数的真值。比如， 01101 和 11101 是两个机器数，而它们的真值分别为 +1101 和 -1101。

根据小数点位置固定与否，机器数又可以分为定点数和浮点数。 通常，使用定点数表示整数，而用浮点数表示实数。后面我们讨论的是定点数，即有符号整数。

有符号整数的表示：原码、反码、补码

注：只有有符号整数才存在不同的编码方式，无符号数没有原码、反码和补码一说。

下面以字长 8bit 的机器数来举例。

原码

将真值中的 “+” 、“-” 分别用 1、0 代替就叫做数的原码形式，简称原码。

1
2
[+1]原 = 0000 0001
[-1]原 = 1000 0001
反码

对正数来说，其反码和原码的相同。负数的反码是在其原码的基础上, 符号位不变，其余各个位取反。

1
2
[+1] = [00000001]原 = [00000001]反
[-1] = [10000001]原 = [11111110]反
补码

对正数来说，其反码和原码的相同。负数的补码是在其原码的基础上, 符号位不变, 其余各位取反, 最后加1(也就是反码末位加 1)。

1
2
[+1] = [00000001]原 = [00000001]反 = [00000001]补
[-1] = [10000001]原 = [11111110]反 = [11111111]补

综上所述，对于正整数而言，原码、反码、补码都一样，只有负整数原码、反码、补码表示不同。

计算机中有符号整数的存储

我们都知道, 在数学上减一个数等于加上这个数的相反数，所以有符号整数的加减法运算都可以视为加法运算。这没有什么问题，但是对于二进制存储的有符号整数，由于 “符号位” 参与运算便会有一些问题：

  1. 若使用原码计算，涉及到负整数时就必须对符号位做特殊处理，并且还有 +0 和 -0 的问题；
  2. 若使用反码计算，符号位不需要特殊处理，但由于反码与原码的取值范围相同，所以也有 +0 和 -0 的问题；
  3. 使用补码则没有上述问题，但是补码的取值范围与原码不同，补码表示的最小值没有对应的原码。

注：使用原码和反码存储数都会存在一个 +0 与 -0 的问题，比如 8bit 字长的有符号整数，[0000 0000]原 和 [1000 0000]原 都表示0，[0000 0000]反和[1111 1111]反 都表示0，虽然能够理解，但这实际上没有什么意义。用补码表示时，[0000 0000]补 表示 +0，没有 -0；[1111 1111]补 表示 -1， [1000 0000]补 表示 -128，可以多保存一个最小值，所以 32 位 int 类型, 可以表示范围是: [-2^31, 2^31-1]，用原码或者补码都只能表示 [-2^31 + 1, 2^31-1]。

在计算机中，加减法是基础运算，需要设计的足够简单。对于有符号整数，若让计算机执行加减法时还要去识别 “符号位” ，那么光基础电路至少就得设计两套，显然是复杂了。加上数字电路实现加法电路比减法电路要简单（不要问为什么，我已经还给大学老师了），所以在现代计算机中有符号整数是采用补码存储的（据说历史上曾经生产过使用反码存储的计算机）。

注：后面的内容主要参考了 《原码, 反码, 补码详解》一文，非常感谢原作者的论证，受益匪浅。

为什么要使用补码，其原理涉及到一些数学知识：反码、补码引入的数学基础是模运算 和 “同余”。

正数的模运算很简单，负数的模运算我们不常用，反正我是不知道怎么算的。负数的模运算怎么算，需要从模运算的定义来看：

1
X mod Y = X - Y * floor(X/Y)

举例来说：

1
2
3 mod 5 = 3 - 5 * floor(3/5) = 3 - 5 * floor(0.6) = 3 - 5 * 0 = 3
-2 mod 5 = -2 - 5 * floor(-2/5) = -2 - 5 * floor(-0.4) = -2 - 5 * (-1) = 3

两个整数 a，b ，若它们除以整数 m 所得的余数相等，则称 a，b 对模 m 同余，a、b 互为补数。记作：a ≡ b (mod m)，读着：a 与 b 对模 m 同余。比如：

1
2
3 mod 5 = 3
-2 mod 5 = 3

所以 3 与 -2 对模 5 同余。

好了，我们已经知道如何进行模运算和 “同余” 的定义了，接下来我们来看看怎么将加一个负整数转为加一个正整数。

这涉及到余数的2个定理：

1
2
反身性：a ≡ a (mod m)
同余式相加：若 a ≡ b(mod m)，c ≡ d(mod m)，则a±c ≡ b±d (mod m)

结合同余的定义，有：

1
2
3
4 ≡ 4(mod 5)
-2 ≡ 3(mod 5)
4 - 2 ≡ 4 + 3(mod 5)

4 - 2 与 4 + 3 对模 5 同余，换句话说，选择一个 “合适的模数” ，我们就能把加一个负整数（减法运算）变成加一个正整数（加法运算）。数学支持有了，现在我们来看看二进制表示的有符号整数：

1
4 - 2 = 4 + (-2) = [0000 0100]原 + [1000 0010]原 = [0000 0100]反 + [1111 1101]反

对比一下上面 4 - 2 ≡ 4 + 3(mod 5)，很容易联想到 “[1111 1101]反 和 -2 对模 X 同余” 的结论。如果把 [1111 1101]反 当作原码（正整数的反码与原码相同就不考虑了），则 [1111 1101]原 = -125，不考虑符号位的话是 125，那么 X=127，即:

1
2
3
-2 mod 127 = 125
125 mod 127 = 125
-2 ≡ 125(mod 127)

则 4 - 2 与 4 + 125 对模 127 同余，而它们的余数正是我们需要的计算结果。让有符号整数符号位参与运算溢出以后的结果便是 4 + 125 模 127 的结果（余数），即 4 - 2 = 溢出（4 + 125）。

可以看出，“一个数的反码若不考虑符号位” 其实就是这个数对 “一个模” 的补数，这个模就是字长所能表示的最大值。而用补码表示实际上就是把模变成了字长所能表示的最大值加1。