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

上下文约束

默认围绕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与b关于模m同余。同余的数具备很多性质,其中有一条保持基本运算:

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

0点和12点关于12点同余,5和5当然关于12点同余,那么有:

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

负数的反码

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

取c为1,那么

即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举例子:

取c为1,那么

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

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

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

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

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

)在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减去该数再加一。

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

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

如果说unsigned int的存储形式和int的一致,那意味着int负数转换成unsigned int的值就是它补码的字面值。我们使用Solidity语言程序验证,在验证之前,先要安装ganache-clisolidity-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);
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

扫码关注云+社区

领取腾讯云代金券