Number Systems

计算机硬件使用 0 和 1 来存储信息。当我们需要存储的信息为数字（Number）时，我们可以使用不同的编码方式（Encoding）将相同的一个数字存储为不同的 01 排列，以满足不同的需求。同样，在面对计算机硬件中已经存在的 01 排列时，我们可以使用不同的解码方式（Decoding）将相同的 01 排列理解为不同的数字。

本文将对常见的整数编码解码方式（又称表示方法，Representation）进行梳理，并重点关注它们是如何从需求中诞生的。

Bits/Context

在所有一切讨论开始以前，我们需要区分清楚两个概念：01 排列和编码解码方式。

单单从计算机硬件角度看，硬件中的 01 排列是没有意义的，它们只是单纯的 0 和 1。同样，硬件对 01 排列进行的一系列运算也是没有意义的，硬件只是根据数字电路的设计机械地对输入的 01 排列进行处理，最后输出另一串 01 排列。

01 排列的意义是由人类赋予的，准确来说，是编码解码方式赋予的。编码解码方式规定了人类在看到一串特定的 01 排列后，该用怎么样的方式进行理解。

Unsigned Numbers

面对一堆 0 和 1，最自然的解码方式就是把这些 0 和 1 当作一个正常的二进制数（Binary Number)。比如看到 01 排列 0101，我们会自然地将其当成二进制数 0101。

Addition

当我们想相加两个数字 0001 和 1001 的时候，我们很自然会使用二进制加法：

  1
0001
1001
----
1010

这样的二进制加法在计算机中是使用数字电路实现的。这样进行二进制加法的数字电路叫做加法器。

• 加法器不关心解码方式

  需要注意的是，加法器并不关心两个输入的 01 排列使用的解码方式。加法器只是机械地对输入的 01 进行操作，最后得到输出的 01 结果。

  当然，我们人类是关心 01 排列的含义的。当我们人类使用 Unsigned Number 这种编码解码方式来看待加法器的操作时，我们会把 0001 1001 1010 排列理解为数字 0001 1001 1010。

• 溢出（Overflow）

  计算机硬件一般使用有限的空间存储 01 排列。比如一台计算机只能一次存储 4 个 0 或 1，这时如果我们将 01 排列 1000 1000 输入加法器，加法器只能输出 01 排列 0000，第 4 位（从第 0 位开始）的 1 因为存不下，所以被丢掉了。这样的现象叫做溢出（Overflow）。

Drawback

我们很快会发现，这样的编码方式只能对正数进行编码，不能对负数进行编码。

为了表示负数，我们需要用一种方式在 01 的排列中表示出正负。

Sign/Magnitude Numbers

正负是 2 种状态，一位 0 和 1 也是 2 种状态。所以我们可以在 01 排列中用一位表示正负信息，用剩余的 01 排列表示绝对值大小。比如规定最高位表示正负信息，0表示正，1表示负，剩下的几位表示绝对值。这就是 Sign/Magnitude 编码方式。

用这种编码方式，-1 将被表示为 1001，1 将被表示为 0001，非常直观。

Drawback

但是这种编码方式有几个问题：

• 正 0 和 负 0

  根据这种编码方式，0000 表示正 0，1000 表示负 0。但是整数里只有一个整数 0。一个整数存在两种编码，在进行计算时可能会带来不必要的麻烦。

• 不适用加法器

  加法器对 Unsigned Number 编码解码方式是适用的，我们希望对 Sign/Magnitude 编码解码方式也适用，因为这样就可以复用加法器，而不需要再重新设计一套数字电路。

  假设我们现在将 -1 加上 1。它们的二进制表示分别为 1001 和 0001。将这两个 01 排列输入加法器，加法器输出的 01 排列是 1002。使用 Sign/Magnitude 解码方式，得到数字 -2。很明显，加法器不适用 Sign/Magnitude。

  所以我们如果要采用 Sign/Magnitude，我们必须重新设计一套数字电路来进行加法操作。

  实际上，我们可以思考一下需要的加法数字电路的特点：

  如果 01 排列的最高位相同，就把它们的其余位相加，最高位不变。其余位相加，同样可能产生溢出；

  如果 01 排列的最高位不同，首先比较它们的其余位谁大，然后用大数减小数，结果的最高位和大数相同。

  我们也可以思考一下需要的减法数字电路的特点：

  假设排列 aaaa 要减去 bbbb，我们可以将 bbbb 的最高位取反得到b'bbb。这样我们就可以将 aaaa 和 b'bbb 输入上面所说的加法数字电路。所以实际上，减法可以复用上面说的加法数字电路。

  但是，这样一套加法数字电路仍然非常复杂，尤其是中间还涉及到大数减去小数的减法。计算机科学中一个非常重要的思想就是「复用」。在这里，我们同样希望适用于 Unsigned Number 的加法器可以适用于 Sign/Magnitude，但经过上面的讨论，答案是不适用。

  我们可以尝试一下，看看能不能找到一种编码解码方式，它既可以表示负数，又可以适用加法器。

Ones’ Complement

两个例子

• 正数加负数等于正数

  我们先观察一个正数加负数结果为正数的例子，也就是被减数大于减数。我们可以尝试做变换，使减法变成加法。比较有用的变换是下面这种：

  0001 0000 - 0000 0100 =
  0001 0000 + (1111 1111 - 0000 0100) - 1 0000 0000 + 1
  

  这样的变换是绝对成立的，它只是先加上 1111 1111，然后把这个加上的 1111 1111 通过减 1 0000 0000 加 1 的方式减去。

  我们可以看到 0001 0000 + (1111 1111 - 0000 0100) 绝对要进位，因为被减数大于减数。而这个进的位正好可以用 1 0000 0000 减掉。最后面还有个 +1，我们就可以说把这个进位放到最低位上。

  总结起来，如果一个正数加负数结果为正数，那么我们可以给负数做 1111 1111 - 负数绝对值 这样的变换。这个变换同样可以通过对负数绝对值每一位取反得到。变换好了以后，正数和负数的变换相加，然后在最低位加 1 就能得到结果。可以看到，每一步都没有用到减法。

• 正数加负数等于负数

  现在我们试试正数加负数结果为负数的例子，也就是被减数小于减数。我们同样给负数（减数）进行上面的变换，看看能得到什么。

  0000 0100 - 0000 1000 =
  0000 0100 + (1111 1111 - 0000 1000) - 1 0000 0000 + 1 = 结果
  0000 0100 + (1111 1111 - 0000 1000) = 1111 1111 + 结果
  

  我们知道，结果肯定是负数。而 1111 1111 + 结果 就是上面提到的变换。

  所以，在正数加负数结果为负数的例子中，我们也可以对负数（减数）进行变换。正数和负数（减数）的变换相加以后就是结果的变换。

由变换得到编码方式

• 具体编码方式

  我们可以看到上面提到的这个 1111 1111 - 负数绝对值 变换对负数非常有用。根据上面提到的两个例子，我们可以定义这样的编码方式：

  正数使用 Unsigned Number 方式进行编码，负数使用 1111 1111 - 负数绝对值 的方式进行编码。

• Ones’ Complement 撇号位置

  因为对负数编码时需要多个 1 作被减数，所以这种编码方式叫做 Ones’ Complement，而不是 One’s Complement。

• 实际不用减法，用取反

  另外我们可以发现，1111 1111 - aaaa aaaa 和 aaaa aaaa 每一位取反结果是一样的。为了不使用另外的减法电路，该编码方式通常通过每一位取反完成。

• 验证 Ones’ Complement 是否适用于加法器

  我们重新验证一下上面两个例子。

  在例子 1 中，0001 0000 要加 - 0000 0100，它们的 Ones’ Complement 编码为 0001 0000 1111 1011。这两个 01 排列输入加法器，最高位肯定会进位，加法器会输出 01 排列 1 0000 1011。加法器的输出还需要去掉 1 0000 0000，再加上 1，得到 01 排列 0000 1100，根据 Ones’ Complement 方式进行解码，得到结果 0000 1100，正确。

  例子 2 中，0000 0100 要加 - 0000 1000，它们的 Ones’ Complement 编码为 0000 0100 1111 0111。这两个 01 排列输入加法器，最高位肯定不会进位，加法器会输出 01 排列 1111 1011。根据 Ones’ Complement 方式进行解码，得到结果 - 0000 0100，正确。

• 对加法器的输出处理

  总结一下，两个 Ones’ Complement 编码的 01 排列输入加法器，如果加法器的最高位有进位，那么要把这个进位去掉，然后加上 1，得到的 01 排列用 Ones’ Complement 方式解码；如果加法器的最高位没有进位，那么输出的 01 排列可以直接用 Ones’ Complement 方式解码。

取值范围

我们限定 01 排列是 8 位的，那么 -0 的编码就是 1111 1111，-1 的编码就是 1111 1110，-127 是 1000 0000，-128 是 0111 1111；+127 是 0111 1111，+128 是 1000 0000。可以看到，产生了重复。为了根据最高位判断符号，所以 8 位 01 排列用这种解码方式取值范围是 -127～+127。

另外主要注意，0 有两种表示方法。

另外三种情况

上面的两个例子中，我们已经讨论了正加负等于正，以及正加负等于负这两种情况，整数相加还有下面三种情况：

• 正数加正数等于正数

  这种情况没什么好讨论的，需要注意的是可能会产生溢出。

• 负数加负数等于负数

  - 0000 1000 - 0000 0100 = 结果
  (1111 1111 - 0000 1000) + (1111 1111 - 0000 0100) = 1111 1111 + 结果 + 1 0000 0000 - 1
  (1111 1111 - 0000 1000) + (1111 1111 - 0000 0100) - 1 0000 0000 + 1 = 1111 1111 + 结果
  

  上面例子中，- 0000 1000 要加 - 0000 0100，它们的 Ones’ Complement 编码为 1111 0111 1111 1011。这两个 01 排列输入加法器，最高位肯定会进位。因为 1111 1111 - 负数1绝对值 + 1111 1111 - 负数2绝对值 进位的条件是，两个负数绝对值加起来小于等于 1111 1110，即 254，而任何一个负数的绝对值小于等于 127，满足条件。

  加法器会输出 01 排列 1 1111 0010。加法器的输出还需要去掉 1 0000 0000，再加上 1，得到 01 排列 1111 0011，根据 Ones’ Complement 方式进行解码，得到结果 - 0000 1100，正确。

  同样，这种情况可能也会产生溢出。

• 正数加负数等于 0

  0000 1000 - 0000 1000 = 结果
  0000 1000 + (1111 1111 - 0000 1000) - 1 0000 0000 + 1 = 结果
  0000 1000 + (1111 1111 - 0000 1000) = 1111 1111 + 结果
  

  0000 1000 编码为 0000 1000，- 0000 1000 编码为 1111 0111。输入加法器，最高位不进位。加法器输出 1111 1111。进行解码，得 -0，正确。

优点和缺点

如果使用 Ones’ Complement 编码解码方式，进行加法和减法都只需要加法器和取反器，相比 Sign/Magnitude 简单了太多。另外，Ones’ Complement 也可以通过最高位判断正负。

但是，Ones’ Complement 还是存在正 0 和负 0 的问题。

我们可以尝试一下，看看能不能找到一种编码解码方式，能完美解决 Sign/Magnitude 的两个缺点。

Two’s Complement

改进变换方式

Ones’ Complement 编码方式中 0 有两种编码。我们尝试对编码方式进行更改，让 0 只有一种编码。

我们可以对负数绝对值取反后再加一个 1，这样 -0 的 Ones’ Complement 编码 1111 1111 就变成 0000 0000 了。+0 的编码还是 0000 0000。整数 0 就只有一种编码了。

接下来，我们先用这种变换方式尝试一下常见的整数运算情况。

两个例子

• 正数加负数等于正数

  我们观察一个正数加负数结果为正数的例子，也就是被减数大于减数。运算时尽量使用上面提到的变换。

  0001 0000 - 0000 0100 =
  0001 0000 + (1111 1111 - 0000 0100 + 1) - 1 0000 0000 + 1 - 1
  

  我们可以看到 0001 0000 + (1111 1111 - 0000 0100 + 1) 绝对要进位，因为 1111 1111 加 1 肯定会进位，并且被减数大于减数。而这个进的位正好可以用 1 0000 0000 减掉。最后面还有个 +1 和 -1 相互抵消。我们可以说忽略这个进位。

  总结起来，如果正数加负数结果为正数，那么我们可以给负数做 1111 1111 - 负数绝对值 + 1 这样的变换。变换好了以后，正数和负数的变换相加，进位忽略就可以得到结果。可以看到，每一步都没有用到减法。

• 正数加负数等于负数

  现在我们试试正数加负数结果为负数的例子，也就是被减数小于减数。我们同样给负数（减数）进行上面的变换，看看能得到什么。

  0000 0100 - 0000 1000 =
  0000 0100 + (1111 1111 - 0000 1000 + 1) - 1 0000 0000 + 1 - 1 = 结果
  0000 0100 + (1111 1111 - 0000 1000 + 1) = 1111 1111 + 结果 + 1
  

  我们可以看到 0000 0100 + (1111 1111 - 0000 1000 + 1) 绝对不会进位，因为被减数减减数结果肯定小于等于 -1。

  我们知道，结果肯定是负数。而 1111 1111 + 结果 + 1 就是上面提到的变换。

  总结起来，在正数加负数结果为负数的例子中，我们也可以对负数（减数）进行变换。正数和负数（减数）的变换相加以后就是结果的变换。

由变换得到编码方式

• 具体编码方式

  我们可以定义这样的编码方式：

  正数使用 Unsigned Number 方式进行编码，负数使用 1111 1111 - 负数绝对值 + 1 的方式进行编码。

• Two’s Complement 撇号位置

  因为对负数编码时，实际上是 2^n - 负数绝对值，只有一个 2，所以这种编码方式叫做 Two’s Complement，而不是 Twos’ Complement。

• 验证 Two’s Complement 是否适用于加法器

  我们重新验证一下上面两个例子。

  在例子 1 中，0001 0000 要加 - 0000 0100，它们的 Two’s Complement 编码为 0001 0000 1111 1100。这两个 01 排列输入加法器，最高位肯定会进位，加法器会输出 01 排列 1 0000 1100。加法器的输出还需要去掉 1 0000 0000，得到 01 排列 0000 1100，根据 Two’s Complement 方式进行解码，得到结果 0000 1100，正确。

  例子 2 中，0000 0100 要加 - 0000 1000，它们的 Two’s Complement 编码为 0000 0100 1111 1000。这两个 01 排列输入加法器，最高位肯定不会进位，加法器会输出 01 排列 1111 1100。根据 Two’s Complement 方式进行解码，得到结果 - 0000 0100，正确。

• 对加法器的输出处理

  总结一下，两个 Two’s Complement 编码的 01 排列输入加法器，如果加法器的最高位有进位，那么无视该进位，得到的 01 排列用 Two’s Complement 方式解码；如果加法器的最高位没有进位，那么输出的 01 排列可以直接用 Two’s Complement 方式解码。

取值范围

-1 是 1111 1111，-127 是 1000 0001，-128 是 1000 0000，-129 是 0111 1111。

+1 是 0000 0001，+127 是 0111 1111，+128 是 1000 0000。

为了保证负数最高位是 1，取值范围为 -128～+127。

另外需要注意，整数 0 的编码只有 0000 0000。

另外三种情况

上面的两个例子中，我们已经讨论了正加负等于正，以及正加负等于负这两种情况，整数相加还有下面三种情况：

• 正数加正数等于正数

  这种情况没什么好讨论的，需要注意的是可能会产生溢出。

• 负数加负数等于负数

  - 0000 0100 - 0000 0100 = 结果
  (1111 1111 - 0000 0100 + 1) + (1111 1111 - 0000 0100 + 1) = 1111 1111 + 1111 1111 + 1 + 1 + 结果
  (1111 1111 - 0000 0100 + 1) + (1111 1111 - 0000 0100 + 1) = 1111 1111 + 1 + 结果 + 1 0000 0000
  (1111 1111 - 0000 0100 + 1) + (1111 1111 - 0000 0100 + 1) - 1 0000 0000 = 1111 + 结果 + 1
  

  上面例子中，- 0000 0100 要加 - 0000 0100，它们的 Two’s Complement 编码为 1111 1100 1111 1100。这两个 01 排列输入加法器，最高位肯定会进位。因为 1111 1111 - 负数1绝对值 + 1 + 1111 1111 - 负数2绝对值 + 1 进位的条件是，两个负数绝对值加起来小于等于 1 0000 0000，即 256，而任何一个负数的绝对值小于等于 128，满足条件。

  加法器会输出 01 排列 1 1111 1000。加法器的输出还需要去掉 1 0000 0000，得到 01 排列 1111 1000，根据 Two’s Complement 方式进行解码，得到结果 - 0000 1000，正确。

  同样，这种情况可能也会产生溢出。

• 正数加负数等于 0

  0001 0000 - 0001 0000 =
  0001 0000 + (1111 1111 - 0001 0000 + 1) - 1 0000 0000 + 1 - 1
  

  0001 0000 编码为 0001 0000，- 0001 0000 编码为 1111 0000。输入加法器，最高位一定进位。加法器输出 1 0000 0000，去掉 1 0000 0000，得到排列 0000 0000。根据 Two’s Complement 方式进行解码，得到结果 0000 0000，正确。

优点

通过上面的讨论，我们可以看到 Two’s Complement 方式完美解决了 Sign/Magnitude 的两个缺点。而 Two’s Complement 也是所有现代计算机编码有符号数的方式。