数字在计算机中的“硬币表示”

上篇博文 引出了“硬币模型”,从“抛硬币”的角度描述了计算机数据的最本质属性。同时也介绍了为若干硬币赋予现实意义、实现更多数据在计算机表示的基本思路。

接下来我也会具体展开介绍一下数字、文字、音频、图像、视频在“硬币体系”下的表达,为你带来更直观的印象,本篇将重点介绍“数字”的表达。

1. 放下“硬币”

读过上篇博文的你,大概已经有了解我们说的“硬币体系”,它其实就是数学角度的 “二进制位”,这里先明确一个设定:

二进制位的值抛硬币结果
0反面
1正面

为了更好地表达更复杂的概念,这时候的你需要逐渐放下“硬币”这样的模型,去适应那由符号 0 和 1 构成的数学世界啦。

2. 表达数字

我们用“二进制位”表达数字,也是和上文所说为硬币的正反状态赋予 “意义体系” 的思路。

这里介绍两个最常见的关于在计算机中表达数字的“意义体系”,一个是表达整数的补码表示法,一个是表达小数的浮点表示法

3. 整数与补码表示法

表达整数,面临的第一个问题是:我们常用的整数,范围是从负无穷到正无穷,个数也是无穷的。而一台电脑不管能提供多少硬币,它都是有限的。自然,计算机的“硬币体系”所能表达的数字范围也是有限的。

我们必须接受一个现实:面对整数,计算机只能表达其中有限的一部分。

当然,从使用者角度,一般我们也不会用到无限大,所以只要硬币足够多,提供的状态数量还是足够日常的表达需要的。比如说,假如我们用 4 Bytes 也就是 32 枚硬币去表达一个数字,它能提供 $2^{32} = 4294967296$ (约43亿)个状态,平分下来可以用来表达 -21.5亿 ~ 21.5亿;若我们再加 4 Bytes,有了 8 Bytes (64枚硬币),就能提供 $2^{64} \approx 1.84 * 10^{19}$ 种状态,这个量级可以说是远远超出了日常用到的数量。所以说,虽然有限,但并不代表不够用。

Windows 计算器中的 64位二进制数

我们知道,整数分为正整数负整数0,要用固定的状态数去表达整数,我们得有个约定的规则去分配这些状态数,最好能够保持整数的一部分运算性质。

补码表示法也正是在这个背景下,表达整数的一种规则,这里也简单介绍一下。

首先,补码规则的前提是,数字需要写成二进制形式(也就是说要能够通过摆若干个正反面硬币来表达),并且划定一个固定的位数(表示一个数字用多少枚硬币),比如说 4位、8位、16位、32位、64位等等。

然后是具体规则:

  1. 对于正数和 0 来说,它的补码即这个数字原始的二进制表达。
  2. 对于负数,它的补码是一个能与它的绝对值“互补”的数。

只是说“互补”自然是看的一脸懵逼的,这里我们用我们生活中常见的模型,做进一步解释。

3.1 钟表的运算模型

“补码”本质上是依赖某种类似钟表的模型设计的规则,假设我们有一个只有秒针的表,如图。

只有秒针的表

我们知道,表盘中有 60 个刻度,每一个刻度代表着从 0 - 59 中的一个数字;每过一秒秒针往前跳动一个刻度,假设我们从 0 出发,经过 20 秒,跳动二十个刻度,指针指向 20;再过 30 秒,指针指向 50。

时间再往后 20 秒,秒针再跳 20 格,它该指向哪里呢?70?显然不是,表盘没有 70 这个刻度,结合生活经验,我们知道它会停在 “10” 这个刻度上。

进一步说,无论你往前跳多少,只要你还在表盘内,每经过一次 60 就归零一次(触发一次进位),结果会一直在 0 - 59 之间循环。用数学的话来说,每超过 60 你就得减去 60,运用小学除法,最终的结果就是:

(“在第几个刻度出发” + “变化的刻度数”) 除以 “表盘总共的刻度数” 得到的 余数

在这个表盘中,我们只关心余数,顾名思义,这种运算也叫做“求余运算”,有个专门的运算符叫 $mod$,这时,求上面的表盘停在哪个刻度的计算过程,用数学符号表示就是:

$$ (0 + 20 + 30 + 20) \space mod \space 60 = 10 $$

表盘的体系中,刻度与刻度之间的运算,实际上都可以化为秒针的前后跳动,最后根据秒针跳动的刻度数 $mod\ 60$ 得到秒针该停下来的位置,对应的刻度即为运算结果。

3.2 刻度的分配策略

上文我们说到,负数在补码中的表达,是一个与它的绝对值“互补”的数,了解了钟表的刻度模型以后,接下来就是如何利用这个模型的规律,在钟表中分配一些属于负数的“刻度”。

钟表里 0-59 这六十个刻度,每满足一个 60 就会归零,化为两数相加,就是 $1+59=60$,$2+58=60$,$3+57=60$... 有没有发现规律所在?

我们用数学符号严格地把这样的规律表达出来,首先从钟表刻度的角度出发:

$$ (1+59)\ mod\ 60 = 0 \\ (2+58)\ mod\ 60 = 0 \\ (3+57)\ mod\ 60 = 0 \\ ... \\ (29+31)\ mod\ 60 = 0 \\ (30+30)\ mod\ 60 = 0 $$

在整数的体系下出发:

$$ (1+(-1)) = 0 \\ (2+(-2)) = 0 \\ (3+(-3)) = 0 \\ ... \\ (29+(-29)) = 0 \\ (30+(-30)) = 0 $$

也就是说,我把钟表的后三十个分给负数,一部分整数的运算就成为了现实!

还有一个问题,刻度 30 只有一个,我不可能让它既表示 +30 又表示 -30,按设计补码的思路,我们把它分配给 -30(后面我会解释为什么)。

这时候刻度是这么分配的:

  1. 钟表的零刻度分给整数中的 0
  2. 刻度 1 ~ 29 分给整数中的 1 ~ 29
  3. 刻度 59 ~ 30 分给整数中的 -1 ~ -30

于是我们实现了 $-30 \to 29$ 这六十个数字在钟表体系下的分配。

把钟表刻度分配给整数

3.3 实际的补码

计算机的运算过程也是类似的钟表结构,为了简单直观,这里我们以 4 个二进制位为例。

想象一下,我们有 4 枚硬币,可以构成 4 位二进制数,共有 $2^4 = 16$ 种正反面组合的情况,我们按照钟表的模型,画出对应的表盘。

4位二进制数的表盘

此时你可以观察一下它们的对应关系,我们把补码与对应的十进制数列成表格:

补码十进制
01117
01106
......
00102
00011
00000
1111−1
1110−2
......
1001−7
1000−8

除去 10000000,观察剩下的数字对应补码的首位,你可能会发现,补码里的正数第一位都是 0,补码的负数第一位是 1。为了运算电路实现的方便,这里我们就把第一位约定为“符号位”,这样,剩下的 1000 就分给负数了。这就是为什么补码规则下 1000 对应了 -8 而不是 +8

到这里,我们了解到了计算机表示整数的机制,当我们用更多的二进制位(上面说到的 8 位、16位、32位、64位),计算机的“钟表”就有更多的“刻度”可以提供给我们,就能表示更大的整数范围。现在流行的电脑、手机等设备都是 64 位了,上文有提到,它能提供的“钟表”有 $2^{64} \approx 1.84 * 10^{19}$ 个“刻度”,意味着至少可以表示 $\pm\ 9.2 * 10^{18}$ 的整数,日常绝对是够用了。

严格来说,计算机中补码依赖的上述钟表的运算模型属于 “同余”的范畴,我们叫它“整数”,只是因为同余的运算性质和整数类似,就像上文所说的“足够用”。这里只做蜻蜓点水,有兴趣深入的朋友可以自己搜索学习。

关于补码,这里还有一个有趣的小漫画:我男朋友是个程序员# 2 之《噩梦》

3.4 计算器的 “程序员” 模式

若你对补码感兴趣,还可以用电脑自带的“计算器”软件来手动转换,微软 Windows 系统提供了一个计算器软件(它是开源的),首先我们大概认识一下界面。

Windows 计算器 - 程序员模式

其中需要解释的概念是字长 代表电脑一次处理运算事务的单位,字长即为这个单位有几个二进制位组成,我们可以理解为一个钟表有多少刻度。日常用到的字长分别有个名字:Byte, Word, DWord, QWord,列一个表格介绍下:

名字全称位数“刻度”数
Byte(字节)-82^8
Word(字)-162^16
DWord(双字)Double Word322^32
QWord(四字)Quadruple Word642^64

切换到二进制输入模式,点击字长切换,我们可以直观地看到可用的“硬币数量”的变化。

计算器中 DWord 的位数

4. 小数与浮点表示法

上面我们介绍了整数的表示,想要表示小数的话,我们需要定义的状态范围已经从整数扩展到了实数。

前面已经说过,计算机的二进制体系(“硬币体系”)所能表达的状态是有限的。整数的无限在于没有上限和下限,扩展到实数范围,它的无限除了上下限外,小数的本身也是“无限”的。这里的无限已经无孔不入,不可能再通过类似补码这样限制范围的方式解决。我们怎么用计算机的有限的状态去接近这无限的数字个数,便是这里最最核心的问题。

想通过“有限”去接近无限,也就意味着有所取舍。在前人的研究下,设计了一种名为浮点数 (float point number) 的表示法来表示小数。

因为浮点数本身较为复杂,这篇小小的科普文章是无法承载,所以这里的目标是带来一个基本的印象,若有进一步的兴趣,可以自行阅读参考资料、在网上搜索学习。

4.1 “乘2”与移位

在继续介绍浮点数前,需要有一点计算机二进制位运算的基础。我们知道,在计算机中,所有的信息都是通过“二进制位”的组合去描述的。它在数学角度表现为类似 010101 这样的数字。

运算方面,若你有仔细观察过数字,你可能会注意到,十进制整数里面,我们每在数字末尾添一个 0,数字的值就 $*\ 10$,每砍掉末尾的一位,数字的值就 $÷\ 10$。比如说,$1230 = 123*10$,$123 = 1230 ÷ 10$。

二进制数一样有类似的规律,我们每在一个二进制位末尾添一个 0,数字的值就 $*\ 2$,砍掉末尾的一位,数字的值就 $÷\ 2$。

用枯燥的数学语言表示如下:

$$ 101_2 = 1*2^2+0*2^1+1*2^0 = 5 \\ 1010_2 = 1*2^3+0*2^2+1*2^1+0*2^0\\ = 10_{10} = 5*2 $$

注:下标 $a_2$ 代表采用 2 进制给 a 计数,下标 $a_{10}$ 代表用 10 进制给 a 计数,省略下标代表都是十进制)

我们还可以把末尾添一个 0 理解位小数点往右移动一位,砍掉末尾一位,理解为小数点往左移动一位,然后丢掉小数点背后的部分。

从这个角度来看,移位操作也意味着小数点的移动,这也是浮点数中“浮点”的含义,无论二进制还是十进制。在十进制中,$\times 10^n$ 意味着小数点向右移动 n 位;在二进制中,$\times 2^n$ 同样意味着小数点向右移动 n 位。

唯一不同的是,二进制移位运算已经在机器层面实现,我们想要的十进制运算也是依赖它进行的。

4.2 浮点数基本结构

现在我可以正式地介绍浮点数了,和整数一样,首先要确定一次用多少个二进制位(硬币)来表达浮点数。常用的浮点数用到的二进制位个数有两种,32位和64位,这里先用 32 位(4 bytes)来说吧。

首先是分工,浮点数由 3 部分组成:符号位(sign)指数(exponent)有效数位(fraction)

32 个二进制位的分配如下:

  1. 分一个给符号位,符号位为 1 时代表负、为 0 时代表正。
  2. 然后分 8 个位给指数,这个数参与最后的求值过程。
  3. 剩下还有 23 个位,分给有效数位,有效数位本身有 24 位,规则规定第一位一定是1,那就不需要再储存,省下1位,剩下23位实际储存。

这三部分各自储存了一个数字,最后的数值计算遵循如下规则:

$$ value = sign\times fraction \times 2^{exponent} $$

上一节我们提到,$\times 2^n$ 相当于小数点向右移动 n 位,所以说,影响到精确度的关键,就在于有效数字 $fraction$,$exponent$ 影响的是数值的大小。

一张图片概括浮点数的求值过程:

图源维基百科“单精度浮点数”词条

4.3 浮点数类型

在上世纪六、七十年代,计算机公司的浮点数千差万别,无论是表达浮点数的位数、还是分配的规则,它们没有固定的标准,在信息交换的过程带来了混乱。

为了统一这种混乱,电气电子工程师学会 制定了IEEE 二进制浮点数算术标准(IEEE 754),确定了浮点数各个细节的规范。

在 IEEE 754 标准中,上一节所介绍的 32 位浮点数规则有个确定的名字,叫做 单精度浮点数

对应还有双精度浮点数,它使用 64 位(8 bytes)来存储一个浮点数,相比于单精度浮点数,它可以存储更多的有效数字、更大的指数,意味着更精确、能表示数字的范围更大。双精度浮点数的分配方案如下。

图源维基百科“双精度浮点数”词条

4.4 精度问题

浮点数是二进制的,有的十进制数字在转换为二进制数的时候可能会出现“无限循环小数”的情况,导致无法完全存储,依赖浮点数运算时会产生误差。

下面是一个 Python 的例子,我们发现,0.1+0.2 其实并不总是等于 0.3,通过括号改变运算顺序,竟会影响到最后的结果:

0.1 与 0.2 与 0.3 的故事

Python 的数字默认用了双精度浮点数,也就是说,转换成二进制后的精确值只能保留到小数点 52 位,0.1 与 0.2 对应的二进制的值如下。

0.1 -> 0.0001100110011001100110011001100110011001100110011001
0.2 -> 0.0011001100110011001100110011001100110011001100110011

实际上除了 0.5 外,0.1-0.9 中的数字在二进制角度都会因为无限循环导致出问题(你可以试试),浮点运算最终给我们的,是一个近似值。换句话说,浮点运算会丢失精度,这是我们使用时需要注意的。

5. 参考资料

  1. 补码 - 维基百科
  2. What is modular arithmetic? - Khan Academy
  3. 同余运算及其基本性质 | Matrix67: The Aha Moments
  4. 补码10000000为什么可以表示-128? - 知乎
  5. 字 (计算机) - 维基百科#%E5%AD%97%E9%95%BF%E5%AE%B6%E6%97%8F)
  6. IEEE 754 - 维基百科
  7. 单精度浮点数 - 维基百科
  8. 双精度浮点数 - 维基百科
  9. JavaScript浮点数的精度问题深究 - 简书
已有 2 条评论
  1. 我记得有种说法说补码可以用同余来理解的~

    不过毕竟学了好长时间了忘差不多了XD

    1. 对对,我这里的钟表其实就是同余,参考链接的可汗学院的那篇文章我觉得说得超级形象~
      这么一说想起来之前看的一个知乎,链接再补上

添加新评论