f\times 2^e

的形式,其中\(-2< f <2\),\(e\)为整数。例如, 二进制小数 11101.1101可以看作\(1.11011101\times 2^{4}\),而0.001101可以看作\(1.101\times 2^{-3}\)。在术语里,我们称\(f\)为尾数,\(e\)为指数。

根据这个发现,我们知道,任何数都可以唯一地表示成符号、尾数和指数的组合。因此,目前通用的浮点数算术标准 IEEE754 标准就规定了浮点数的存储方式为,存储其符号、尾数和指数的组合。其具体标准很枯燥,我们可以用一张图简单地说明一下:

 sign         exponent                          fraction
  |              |                                  |
 --- --------------------------- ---------------------------------------
|   |                           |                                       |
 --- --------------------------- ---------------------------------------

我们常用的浮点数类型包括:

单精度浮点型(float

长度为32位, 其中有23位尾数,8位指数

双精度浮点型(double

长度为64位,其中有52位尾数,11位指数

这些标准乍看上去难以理解,令人头痛,那我们不妨直接来看一个浮点数常见的问题。

浮点数算术的精度问题

我们有一个C程序:

double a = 0.1;
double end = 0.3;
while (a != end) {
   a += 0.1;

这个程序的输出会是怎样的呢?将其编译并运行可以发现,这居然又停不下来了。这是为什么呢?

要想一探究竟,我们可以编写一个辅助函数:

void display_double_in_binary(double f) {
   char *d = (char *)&f;
   for (int i = 0; i < sizeof(f); i++) {
      printf("%.2x ", d[i] & 0xff);
   printf("\n");

这个函数可以输出浮点数的二进制表示。具体的程序位于codes/2-floating-precision.c

我们通过这个辅助函数,可以看到:

Term	end = 0.300000	bin: 33 33 33 33 33 33 d3 3f
Round 1	a = 0.100000	bin: 9a 99 99 99 99 99 b9 3f
Round 2	a = 0.200000	bin: 9a 99 99 99 99 99 c9 3f
Round 3	a = 0.300000	bin: 34 33 33 33 33 33 d3 3f

end的16进制表示是0x3fd3333333333333,而当a加到0.3的时候,它的16进制表示是0x3fd3333333333334。这两者不一致,因此不会进入循环终止条件。

我们上面提到,要想将一个浮点数存储在寄存器中,需要首先将其转化为二进制的小数。那么,0.1转化为二进制小数为0.0001100110011001101...,而0.3转化为二进制小数为0.01001100110011001101...。我们震惊地发现,十进制小数转化成的二进制小数居然不整。

这下就能解释为什么这个程序停不下来了。由于转化的二进制小数不整,因此存储在寄存器中时,发生了截断,产生了一定的误差。那么,在进一步计算时,误差就会累积,从而几乎没有可能真正到达0.3。这就是浮点数算术的精度问题。

这种精度问题在我们实际的生活中会遇到吗?下面,我就介绍一个在Dark Souls速通中被发现的一个Meme Roll Glitch(视频讲解可以看B站搬运的视频《黑暗之魂》中“最疯狂”的skip是如何诞生的的24:45秒开始)。

在Dark Souls中,从高空坠落会受到伤害,当高度高于一定阈值时,人物会死亡。在游戏速通中,玩家希望通过一些地方的跳跃到达后期才能去的地区,从而绕过很多步骤,节省大量的时间。但是,这些跳跃往往高度都非常高,会造成角色的死亡,直接跳显然是不行的。在Meme Roll Glitch发现之后,这个问题终于得到了解决。

提出这个Glitch的玩家发现,当角色的负重在25%与25.000088%之间时,角色可以在高空坠落的过程中不断地翻滚,从而利用翻滚的无敌帧避开坠落的伤害。但是,负重在游戏中的最小计量单位是0.1%,理论上不可能使角色的负重在这个范围内。这就需要浮点数算术的精度问题了。由于浮点数本身采用二进制小数进行存储,所以不可能精确等于其十进制数值。因此通过仔细地调整装备与耐力等级,不断利用浮点数算术的精度误差,最终能使角色处在这一负重范围内,最终实现无伤害坠落。

浮点数能建立全序关系吗?

在一些现代编程语言中,编译器会很聪明地阻止我们干一些事。例如,如果我们想用Rust语言对浮点数的数组进行排序:

#![allow(unused)]
fn main() {
let mut s = [1.0, -3.5, 4.7];
s.sort();

会发现编译不通过,提示"the trait Ord is not implemented for {float}"。这是为什么呢?要解释这一问题,我们不妨先了解一下IEEE754标准里几个特殊的常数(可以参考codes/2-special-numbers.c)。

之前我们提到,存储浮点数时会存储其符号信息。但是,其余数字的存储并不一定会像整数一样使用补码。事实上,在IEEE754标准里,有两个零值:+0.0-0.0

零值存储的值是不同的:+0.0存储的值为0x00000000-0.0存储的值为0x00000080

但是,在比较运算中,+0.0-0.0是相等的。

INFINITY

代表无穷大, 有+INFINITY-INFINITY两个值。

一般可以通过1.0/0.0以及1.0/-0.0得到无穷大值。

在比较运算中,+INFINITY大于所有除了其本身的值;-INFINITY小于所有除了其本身的值。

代表非数值。有+NAN-NAN两个值。

可以通过对-1.0开方等操作得到。

其与任何数都不相等。也就是说,NAN != NAN-NAN != -NAN。也无法进行比较,也就是说,NAN于任何数进行小于、大于的比较,返回结果都是false

介绍了这些特殊的常数,那么,我们就可以解答为什么f32不满足Eq的trait了。

Ord trait,就是全序关系。集合\(X\)上可以建立全序关系,意思就是说:

对于\(X\)中的元素\(a\), \(b\), \(c\)有:

如果\(a\leq b\)且\(b\leq a\),则\(a=b\)

如果\(a\leq b\)且\(b\leq c\),则\(a\leq c\)

对于\(X\)中的任意元素\(a\)和\(b\),都有\(a\leq b\)或\(b\leq a\)

对于我们最常接触的整数来说,这些性质是非常显然的,因此整数可以建立全序关系。

但是,对于我们刚刚提到的IEEE754定义的浮点数类型来说,由于NAN与任何数都不相等,因此浮点数不可以建立全序关系,从而不满足Ord trait。

直观地,我们也可以看出来,NAN这样特殊的数,无法进行比较,从而如果出现在数组中,对其排序是没有意义的。