从补码谈计算机的数值存储和展示

上下文约束

默认围绕8位计算机展开讨论。

问题

在进入正文之前，先提三个问题：

1. 计算机中的数为什么用补码（2's complement）来表示和存储？
2. 补码的计算规则是怎么来的？
3. 计算机是如何区分unsigned int和int？

众所周知，二进制是一种记数系统（类比十进制），而补码就是该系统之上的编码协议。协议是为了无序信息流变得规整，让人能够控制它。从这方面猜测，补码产生的原因是为了最小化硬件设计的成本，这大概也是最初的软件定义硬件（SDH）。

当我们想象比特流的存储过程时，不免好奇自己头脑中的数值概念（尤其是负数和小数）怎么被计算机编码成有意义的比特流？这些比特流如何被正确地计算成另一种比特流？在更高层次上，编程语言中的short, int, unsigned int, long, long long等数值类型是怎样被计算机正确地识别的？

通常，协议是处理复杂度的好方法，但隐藏在协议背后的原因比它本身更有探索的价值。如果你也感同身受，那么阅读下文就是合适的。

为什么用补码？

概念解释

1. 原码[1](True form) 原码是指一个二进制数左边加上符号位后所得到的码，且当二进制数大于0时，符号位为0；二进制数小于0时，符号位为1；二进制数等于0时，符号位可以为0(+0)或1(-0)。
2. 反码[2](One's complement) 反码是带有符号位的二进制数表示；负数的反码是将其对应正数按位取反，正数和0的反码就是该数字本身。
3. 补码[3](Two's complement) 补码也是带有符号位的二进制表示；负数的补码是将其对应正数按位取反再加1，正数和0的补码就是该数字本身。

三者的关系很密切，是1对1的单射关系。准确地说，补码下可表示的最大负数没有对应的原码和反码。具体原因，待会儿做详细讨论。

从实际应用的角度提问，现代计算机中数据的存储形式是原码、反码还是补码？这个问题其实可以规约到另一个问题上：哪种存储形式最有利于计算机进行运算？从这个角度思考就不难得出答案，当然是补码，不然，要是原码和反码都够用，为啥设计出补码？

那么，为什么原码和反码不够用？单独从数据表示来看是无法得出结论的，需要从计算的角度思考。我们都知道，二进制是以2为基数的记数系统，和十进制、六十进制的记数本质相同。在最开始，记数系统中是没有负数的，引入负数是为了统一概念相反的事物。比如：收入和支出，支出就可以视为负的收入。如果用恒等式表达收支平衡收入 = 支出，将支出移项到左边就得变号收入-支出 = 0，换句话说，收入+(-支出) = 0，此时表达了总收入为0这个事实。相同的概念对于运算的意义重大，以前需要设计减法的运算规则，现在用加法规则就可以替代。在人类看来，这意味着概念的统一，而对于计算机而言，这简化了ALU（算术逻辑单元）中集成电路的设计。

既然如此，负数在二进制中的表示就尤为重要。按照原码的定义，-1的二进制表示是1000 0001，那么计算1-1，也就是计算0000 0001 + 1000 0001 = 1000 0010，这个数表示的是十进制中的-2。1-1=-2当然是错的，它为什么是错的呢？因为符号位也参与运算了，上面的算式其实表达的是1+129=130这个算式。

看到这里，或许需要思考的是数的表示和它们之间的运算是不对称的疑问？究其缘由是，数在计算机中表示是人为定义的，我们规定了左边的1是符号位，但是ALU不知道，而且也不应该知道。为什么呢？因为人是善变的，后面还会出现无符号数，那时候左边的1可就不能视作符号位。

在继续探索之前，我们先补充点数学知识。

同余

当两个整数除以同一个正整数，若得相同余数，则这两个整数同余[4]。记为：

a\equiv b \pmod m

读作a与b关于模m同余。同余的数具备很多性质，其中有一条保持基本运算：

\left.{ \begin{matrix} a\equiv b{\pmod {m}}\\c\equiv d{\pmod {m}}\end{matrix} }\right\} \Rightarrow \left\{{ \begin{matrix} a\pm c\equiv b\pm d{\pmod {m}}\\ac\equiv bd{\pmod {m}} \end{matrix} }\right.

我们用这个性质来反观一下日常生活中的12小时制计时法。

\begin{matrix} 0\equiv 12{\pmod {12}} \\ 5\equiv 5{\pmod {12}} \end{matrix}

0点和12点关于12点同余，5和5当然关于12点同余，那么有：

0\pm 5\equiv 12\pm 5{\pmod {12}}

所以5和17关于12同余。当我们说下午5点时，其实也就是在说17点。负数也满足这样的关系，即-5和7关于12同余。

负数的反码

按照定义我们求得-1的反码，1000 0001的反码为1111 1110即254，-1和254相对于255(1111 1111)同余。依据同余的基本性质，

-1\pm c\equiv 254\pm c{\pmod {255}}

取c为1，那么

-1\pm 1\equiv 254\pm 1{\pmod {255}}

即0和255相对于255同余。当然，正确性显而易见。但是，这里面也出现了一个问题，0和255(-0)都是0这个数在反码中的正确表达，这也是负数的反码表示数的范围是[-127, 127]，总数是255个的由来，就像12小时制计时-12和12都是零点的表达，那么对于判0运算而言，就得有两手准备。简单起见，有没有其他方式去掉这种特殊情况呢？于是，补码顺势上位。

负数的补码

由于0和255都是8位计算机中0的合法表达，容易想到的一种方法就是去掉一个，而且还得保留同余的性质。

假如把相对于255的同余变成256的同余是否有帮助呢？此时，0和256就相对于256同余了，但是因为8位二进制只能表示[0, 255]范围的数，再多就溢出了，256是没法表示的。我们还是以-1举例子：

-1\pm c\equiv 255\pm c{\pmod {256}}

取c为1，那么

-1\pm 1\equiv 255\pm 1{\pmod {256}}

0和256同余，即0000 0000和1 0000 0000同余，溢出位1被舍去，就变成了0000 0000。

负数的补码数的表示范围为[-128, 127]，这个-128是怎么来的呢？它的补码表示是1000 0000。要解答这个问题，得看看原码和反码中的0的表示。

先看看原码，左边第一位是符号位，说明它把0~255个数分成了两半，分别是0~127, 128~255。其中，0000 0000和1000 0000都表示0，所以它只能表示255个数。即，-127~127.

类似地，反码中的0000 0000和1111 1111也都表示0，其中1000 0000表示-127，所以它也只能表示255个数。即，-127~127.

但是补码就不同，它里面的0就只有一个0000 0000，而-128和128相对于256同余，但是128(1 0000 0000

_{[2]}

)在8位机器上没法表示，所以干脆把1000 0000直接拿来当-128，可想而知，这个数是没法通过原码取反加1计算出来的，因为它对应的原码并不存在（整数128是不存在的）。

补码的计算规则是怎么来的？

正数的补码就是其本身； 负数的补码是在其原码的基础上, 符号位不变, 其余各位取反, 最后+1

先说说反码计算方式的由来。以-1为例，其原码表示如下：

1000 0001

那么为何对它符号位之外进行取反，就得到了它相对于255(1111 1111)的反码呢？

我们用255减去-1的绝对值，试试看

  1111 1111
- 0000 0001
-----------
  1111 1110

1111 1110就是254，它和1000 0001保留符号位后各位取反的结果一致。这是巧合吗？显然不是，因为1111 1111是8位中最大的数，所以就不存在借位操作，那么各位减下来，位是0的自然得到1，位是1的自然得到0.

-1和254相对于255同余，所以-1是254的补（One's complement）。不信的话，可以去clojure repl中运行下面的表达式。

(mod -1 255) #=> 254

知道到了反码的求值方法的由来，我们不难推断出补码的计算方法。因为256是255+1，取反就是用255减去该数，那么用256减去该数，也就等价于255减去该数再加一。

256-a = 255-a+1

计算机是如何区分unsigned int和int的？

我们已经知道了计算机存储数据全部用的补码的形式，所以从内存中拿出来的数就是补码，那么-1的补码是1111 1111，也就是数2^8-1=255.

如果说unsigned int的存储形式和int的一致，那意味着int负数转换成unsigned int的值就是它补码的字面值。我们使用Solidity语言程序验证，在验证之前，先要安装ganache-cli和solidity-repl.

$ ganache-cli
...
$ solr
Welcome to the Solidity REPL!
> int8 c = -1
> uint8 d = uint8(c)
> d
255

-1的补码是1111 1111，也就是十进制的255，所以从结果中不难得出如下结论：在计算机中，数的存储和表示是分开的，存储的是补码，计算过程也使用补码，但是最后的表示由程序员来决定。所以毫不夸张地说，程序员是规则的缔造者，也是规则的解读者。

顺带一提 solidity中的int和uint是成对的，而且从8, 16, 24, ..., 256，一共有32个。正确性可以通过它的词法分析程序得出来。

//solidity/liblangutil/Token.cpp

if (0 < m && m <= 256 && m % 8 == 0 && positionX == _literal.end())
{
    if (keyword == Token::UInt)
        return make_tuple(Token::UIntM, m, 0);
    else
        return make_tuple(Token::IntM, m, 0);
}