Aug 18, 2017

乱谈整型与浮点

前言

前几天好友终于也入了 C/C++ 的邪教，问起了几个浮点相关的问题，让我终于意识到深陷现代语言泥潭的我早已忘却这些富有趣味但又基础地不能在基础的知识…… 在网上大量查阅相关资料后决定属文以记之。

整型

注：本文中默认 int 长度为 $32$ 位。

无符号整形

这里以 unsigned int 为例（$32$ 位）。unsigned int 就是没有符号的 int，在内存里占用 $4$ Byte，也就是 $32$ bit。很容易得知其能存储的最小值为 $0$，最大值则为 $2^{32} - 1 = 4294967295$。

整形

int 是带有符号的，因此其所占据的第 $0 \sim 31$ 位中第 $31$ 位是用于存储符号的（$0$ 为正，$1$ 为负）。当然你会问，既然所有位均为 $0$ 时变量的值为 $0$，那么符号位为 $1$ 时剩余位为 $0$ 表示的又是什么呢？

这里就要牵扯进 补数 (2’s complement，又称二补数) 的概念了。

一个数字的二补数就是将该数字作比特反相运算（即反码），再将结果加 1。在二补数系统中，一个负数就是用其对应正数的二补数来表示。(Wikipedia，有修改)

而借助二补数性质进行编码的编码系统则简称补码，在补码系统中，我们采用如下方式表示每一个数：

  • 对于非负数，采用原始二进制表示；
  • 对于负数，符号位为 $1$，剩余位采用其补数表示。

为了方便，我们假定一种只有 $8$ 位的整型数据类型来举几个例子（注意下面列出的是对应的补码不是二补数）：

符号位 =
0 1 1 1 1 1 1 1 127
0 0 0 0 0 0 1 0 2
0 0 0 0 0 0 0 1 1
0 0 0 0 0 0 0 0 0
1 1 1 1 1 1 1 1 -1
1 1 1 1 1 1 1 0 -2
1 0 0 0 0 0 0 1 -127
1 0 0 0 0 0 0 0 -128

我们可以容易地总结出以下两点：

  • 取负运算实际上就是取该数的二补数 ($\sim x + 1$)。
  • 有两个数的二补数等于其本身：$0$ 和 $-128$ (溢出了，所以就变成自己了)。

至此，我们也应该理解为什么 $32$ 位整型的取值范围是 $-2147483648 \sim 2147483647$ 了。

浮点

在 C 语言中，浮点数的存储均遵循 IEEE 754 标准。我们不妨结合标准内容来对 float 做一番介绍。

注：并不是在任何情况下浮点数的存储都遵循 IEEE 754 标准！这里仅介绍 IEEE 754 标准。

整体结构

在 IEEE 754 中，浮点数的存储被划为三个部分：符号位 (sign bit)、阶码 (biased exponent)、尾码 (mantissa)。在单精度中它们的长度分别为 $1$ bit、$8$ bit 和 $23$ bit；双精度中它们的长度分别为 $1$ bit、$11$ bit 和 $52$ bit。

为了方便展示，不妨从 Wikipedia 盗两张图下来（遵循 Creative Commons Attribution-ShareAlike License）：

单精度

Single precision

双精度

Double precision

我们知道任意一个二进制浮点数 $V$ 都可以表示为（科学记数法）：

$$ V = (-1)^s \cdot M \cdot 2^E $$

其中，$s$ 是符号位，$M$ 是有效数字（$1 \le M < 2$），$E$ 是指数。

举个例子，对于十进制小数 $0.15625$，其二进制表示为 $0.00101$，用二进制下的科学记数法表示就是 $0.00101 = 1.01 \times 2^{-3}$，那么其符号位为 $0$，有效数字为 $1.01$，尾码为 $.01$，指数为 $-3$。

我们很容易发现，$M$ 的整数部分一定恒为 $1$，那还存什么存？只用存 $M$ 的小数部分就行了，所以尾码就是 $M - 1$。

指数偏移值

依据前文对阶码存储结构的介绍，阶码看起来就像是一个无符号整数。可惜科学记数法中指数是可以为负数的。怎么办？IEEE 就搞了个 指数偏移值 (exponent bias) 出来。指数偏移值就是指浮点数表示法中的指数域的编码值（即阶码的值）为指数的实际值加上某个固定的值（阶码 = $E$ + 指数偏移值）。在 IEEE 754 标准中，指数偏移值的固定大小为 $2^{e - 1} - 1$，其中 $e$ 为储存指数的比特长度。

例如，在单精度中，阶码位长 $e$ 为 8 bit，换算成十进制其可表示范围为 $0 \sim 255$。依据前文，其指数偏移值是 $2^{8 - 1} - 1 = 127$。这样一来，对于单精度浮点数类型指数就可取 $-127 \sim 128$ 了。

规约形式与非规约形式

规约形式 (Normalized numbers)

规约形式的浮点数指的是阶码范围为 $(0, 2^{e} - 1)$ ，且尾码部分最高有效位（即整数部分）为 $1$ 的浮点数。也就是说，前文中我们讨论的浮点数都是规约形式的。

非规约形式 (Denormalized numbers)

为了减小因为下溢 (underflow) 造成的精度损失（换言之，为了使得浮点数可表示的正最小值和负最大值更接近 $0$），IEEE 754 标准中提出了非规约形式浮点数——用于填补最小正数和最大负数与 $0$ 的距离。

非规约形式浮点数的阶码为 $0$，并且尾码为非 $0$。相比规约形式浮点数其最大的不同之处在于，其尾码隐含的整数部分不再是 $1$，而变成了 $0$。另外，IEEE 754 标准规定，非规约形式的浮点数的指数偏移值比规约形式的浮点数的指数偏移值小 $1$。也就是说，最小的规约形式浮点数阶码为 $1$，指数的实际值为 $-126$。而非规约形式的单精度浮点数的阶码为 $0$，依照上述规定其指数的实际值也是 $-126$ 而不是 $-127$。

为什么要这样规定？

我们首先来看看这种规定下非规约形式浮点数能表示的最大正浮点数吧（拿单精度举个例子，双精度是类似的）：

符号位 阶码 尾码
0 0000 0000 111 1111 1111 1111 1111 1111

不难得出，其实际指数 $E = 0 - 126 = -126$，其实际有效数字为 ${0.11111111111111111111111}_2$。因此，二进制下，其表示的实际值为 $V = {0.11111111111111111111111}_2 \times 2^{-126}$。

而对于规约形式浮点数能表示的最小正浮点数：

符号位 阶码 尾码
0 0000 0001 000 0000 0000 0000 0000 0000

不难得出，其实际指数为 $E = 1 - 127 = -126$，其实际有效数字为 ${1.00000000000000000000000}_2$。因此，二进制下，其表示的实际值为 $V = {1.00000000000000000000000}_2 \times 2^{-126}$。

不难发现在这种规定下，最大非规约形式浮点数和最小非规约形式浮点数是连续的。这也是该规定出现的原因。

特殊值

另外，在标准中也定义了几个特殊值：

  • 当阶码和尾码均为 $0$ 时，浮点数表示的实际值为 $\pm 0$；
  • 当阶码为 $2^{e} - 1$且尾码为 0 时，浮点数表示的实际值为 $\pm \infty$；
  • 当阶码为 $2^e - 1$ 且尾码非 0 时，浮点数表示的实际值为 $\text{NaN}$ (Not a Number)。

$\text{NaN}$ 是什么？可以吃吗？

当然不能。$\text{NaN}$ 往往出现于一些无效的计算结果。比如说，对负数进行求平方根运算，返回的结果就是 $\text{NaN}$。

取值范围、精度和间隙

注：本节主要讨论单精度浮点数的取值范围与精度。双精度与之类似，所以请读者自行推导。

取值范围 (Range)

前文中已经介绍过单精度浮点数在存储中的大致结构了。我们先就正浮点数做一下分析：

非规约形式单精度浮点数能表示的最小正值

符号位 阶码 尾码
0 0000 0000 000 0000 0000 0000 0000 0001

不难得出，不难得出，其实际指数 $E$ = 0 - 126 = -126，其实际有效数字为 ${0.00000000000000000000001}_2$。因此，二进制下，其表示的实际值为 $V = {0.00000000000000000000001}_2 \times 2^{-126} \approx 1.40130 \times 10^{-45}$。

规约形式单精度浮点数能表示的最小正值

符号位 阶码 尾码
0 0000 0001 000 0000 0000 0000 0000 0000

不难得出，其实际指数为 $E$ = 1 - 127 = -126，其实际有效数字为 ${1.00000000000000000000000}_2$。因此，二进制下，其表示的实际值为 $V = {1.00000000000000000000000}_2 \times 2^{-126} \approx 1.17549 \times 10^{-38}$。

单精度浮点数能表示的最大正值
符号位 阶码 尾码
0 1111 1110 111 1111 1111 1111 1111 1111

不难得出，不难得出，其实际指数 $E$ = 254 - 127 = 127，其实际有效数字为 ${1.11111111111111111111111}_2$。因此，二进制下，其表示的实际值为 $V = {1.11111111111111111111111}_2 \times 2^{127} \approx 3.40282 \times 10^{38}$。

对于负数也是一样的，这里也不做过多讨论。

双精度也是与此类似的，这里只给出如下结论：

非规约形式双精度浮点数能表示的最小正值

$2^{-1074} \approx 4.94066 \times 10^{-324}$

规约形式双精度浮点数能表示的最小正值

$2^{-1022} \approx 2.22507 \times 10^{-308}$

双精度浮点数能表示的最大正值

$(1 - 2^{-53}) \times 2^{1024} \approx 1.79769 \times 10^{308}$

精度 (Precision) 与 间隙 (Gap)

首先摘抄一段来自 Wikipedia 的原文：

Precision is defined as the minimum difference between two successive mantissa representations; thus it is a function only in the mantissa; while the gap is defined as the difference between two successive numbers.

简单翻译过来就是（不知道翻译错没有）：

精度的定义为两个连续尾数表示之间的最小差值，因此它只是存在于尾数中的功能。而间隙被定义为两个连续数字之间的差值。

对于精度，我们已经可以很容易地回答这个问题了。对于单精度浮点数，尾码有 $23$ 位。$2^{23} = 8388608$，因此单精度浮点数最长（不完整地）可存储小数点后 $7$ 位，但只能完整地存储小数点后 $6$ 位。

而对于间隙出现的原因，我们可以这样理解。

前面我们提到了浮点数内部存储实际上是二进制科学记数法，我们不难发现尾数是有限位的。当指数越来越大时，相邻两尾数表示的两实际值之间的大小也越来越大。这两实际值之间的差也就是间隙。而在间隙之间的数是无法被准确存储下来的。

我们不妨从 Wikipedia 摘录一个展示单精度类型在不同指数下相邻两实际值之间的间隙大小的表格。其中最小值和最大值分别代表当实际指数一定时该浮点数可表示的最小十进制数和最大十进制数。

实际指数 阶码 最小值 最大值 间隙
0 127 1 ≈ 1.999999880791 ≈ 1.19209e-7
1 128 2 ≈ 3.999999761581 ≈ 2.38419e-7
2 129 4 ≈ 7.999999523163 ≈ 4.76837e-7
10 137 1024 ≈ 2047.999877930 ≈ 1.22070e-4
11 138 2048 ≈ 4095.999755859 ≈ 2.44141e-4
23 150 8388608 16777215 1
24 151 16777216 33554430 2
127 254 ≈ 1.70141e38 ≈ 3.40282e38 ≈ 2.02824e31

根据表格，当实际指数为 24 时，相邻两数间的差值已经达到了 2 这么大。因此，$162777217$ 实际上是无法用浮点数表示的，因为事实上它的值会丢失精度至 $162777216$。

相比单精度，由于双精度的尾数总位数更长，故在指数相同时，双精度数与数之间的间隙会比单精度数更小。下面我们也继续从 Wikipedia 摘录一个展示双精度类型不同指数下相邻两实际值间间隙的表格：

实际指数 阶码 最小值 最大值 间隙
0 1023 1 ≈ 1.999999999999999777955 ≈ 2.22045e-16
1 1024 2 ≈ 3.999999999999999555911 ≈ 4.44089e-16
2 1025 4 ≈ 7.999999999999999111822 ≈ 8.88178e-16
10 1033 1024 ≈ 2047.999999999999772626 ≈ 2.27374e-13
11 1034 2048 ≈ 4095.999999999999545253 ≈ 4.54747e-13
52 1075 4503599627370496 9007199254740991 1
53 1076 9007199254740992 18014398509481982 2
1023 2046 ≈ 8.98847e307 ≈ 1.79769e308 ≈ 1.99584e292

这也完美地解释了前几天在学校的 OJ 上水题有的题明明在单精度取值范围内却没法用单精度 A 掉的原因…… 看起来还是我太弱了 orz。

小结

懒得写了（逃

参考文献

排序顺序嘛…… 我才不会告诉你是乱序呢。