10:32 AM
小数在内存中是如何存储的,揭秘诺贝尔奖级别的设计(长篇神文)
小数在内存中是以浮点数的形式存储的。浮点数并不是一种数值分类,它和整数、小数、实数等不是一个层面的概念。浮点数是数字(或者说数值)在内存中的一种存储格式,它和定点数是相对的。

C语言使用定点数格式来存储 short、int、long 类型的整数,使用浮点数格式来存储 float、double 类型的小数。整数和小数在内存中的存储格式不一样。

我们在学习C语言时,通常认为浮点数和小数是等价的,并没有严格区分它们的概念,这也并没有影响到我们的学习,原因就是浮点数和小数是绑定在一起的,只有小数才使用浮点格式来存储。

其实,整数和小数可以都使用定点格式来存储,也可以都使用浮点格式来存储,但实际情况却是,C语言使用定点格式存储整数,使用浮点格式存储小数,这是在“数值范围”和“数值精度”两项重要指标之间追求平衡的结果,稍后我会给大家带来深入的剖析。
计算机的设计是一门艺术,很多实用技术都是权衡和妥协的结果。
浮点数和定点数中的“点”指的就是小数点!对于整数,可以认为小数点后面都是零,小数部分是否存在并不影响整个数字的值,所以干脆将小数部分省略,只保留整数部分。

定点数

所谓定点数,就是指小数点的位置是固定的,不会向前或者向后移动。

假设我们用4个字节(32位)来存储无符号的定点数,并且约定,前16位表示整数部分,后16位表示小数部分,如下图所示:

如此一来,小数点就永远在第16位之后,整数部分和小数部分一目了然,不管什么时候,整数部分始终占用16位(不足16位前置补0),小数部分也始终占用16位(不足16位后置补0)。例如,在内存中存储了 10101111  00110001  01011100  11000011,那么对应的小数就是 10101111  00110001 . 01011100  11000011,非常直观。

精度

小数部分的最后一位可能是精确数字,也可能是近似数字(由四舍五入、向零舍入等不同方式得到);除此以外,剩余的31位都是精确数字。从二进制的角度看,这种定点格式的小数,最多有 32 位有效数字,但是能保证的是 31 位;也就是说,整体的精度为 31~32 位。

数值范围

将内存中的所有位(Bit)都置为 1,小数的值最大,为 216 - 2-16,极其接近 216,换算成十进制为 65 536。将内存中最后一位(第32位)置1,其它位都置0,小数的值最小,为2-16
这里所说的最小值不是 0 值,而是最接近 0 的那个值。

综述

用定点格式来存储小数,优点是精度高,因为所有的位都用来存储有效数字了,缺点是取值范围太小,不能表示很大或者很小的数字。

反面例子

在科学计算中,小数的取值范围很大,最大值和最小值的差距有上百个数量级,使用定点数来存储将变得非常困难。

例如,电子的质量为:

0000000000000000000000000000.9 克 = 9 × 10-28

太阳的质量为:

2000000000000000000000000000000000 克 = 2 × 1033

如果使用定点数,那么只能按照=前面的格式来存储,这将需要很大的一块内存,大到需要几十个字节。

更加科学的方案是按照=后面的指数形式来存储,这样不但节省内存,也非常直观。这种以指数的形式来存储小数的解决方案就叫做浮点数。浮点数是对定点数的升级和优化,克服了定点数取值范围太小的缺点。

浮点数

C语言标准规定,小数在内存中以科学计数法的形式来存储,具体形式为:

flt = (-1)sign × mantissa × baseexponent

对各个部分的说明:
  • flt 是要表示的小数。
  • sign 用来表示 flt 的正负号,它的取值只能是 0 或 1:取值为 0 表示 flt 是正数,取值为 1 表示 flt 是负数。
  • base 是基数,或者说进制,它的取值大于等于 2(例如,2 表示二进制、10 表示十进制、16 表示十六进制……)。数学中常见的科学计数法是基于十进制的,例如 6.93 × 1013;计算机中的科学计数法可以基于其它进制,例如 1.001 × 27 就是基于二进制的,它等价于 1001 0000。
  • mantissa 为尾数,或者说精度,是 base 进制的小数,并且 1 ≤ mantissa < base,这意味着,小数点前面只能有一位数字;
  • exponent 为指数,是一个整数,可正可负,并且为了直观一般采用十进制表示。

下面我们以 19.625 为例来演示如何将小数转换为浮点格式。

当 base 取值为 10 时,19.625 的浮点形式为:

19.625 = 1.9625 × 101

当 base 取值为 2 时,将 19.625 转换成二进制为 10011.101,用浮点形式来表示为:

19.625 = 10011.101 = 1.0011101×24

19.625 整数部分的二进制形式为:
19 = 1×24 + 0×23 + 0×22 + 1×21 + 1×20 = 10011
小数部分的二进制形式为:
0.625 = 1×2-1 + 0×2-2 + 1×2-3 = 101
将整数部分和小数部分合并在一起:
19.625 = 10011.101
可以看出,当基数(进制)base 确定以后,指数 exponent 实际上就成了小数点的移动位数:
  • exponent 大于零,mantissa 中的小数点右移 exponent 位即可还原小数的值;
  • exponent 小于零,mantissa 中的小数点左移 exponent 位即可还原小数的值。

换句话说,将小数转换成浮点格式后,小数点的位置发生了浮动(移动),并且浮动的位数和方向由 exponent 决定,所以我们将这种表示小数的方式称为浮点数。

二进制形式的浮点数的存储

虽然C语言标准没有规定 base 使用哪种进制,但是在实际应用中,各种编译器都将 base 实现为二进制,这样不仅贴近计算机硬件(任何数据在计算机底层都以二进制形式表示),还能减少转换次数。

接下来我们就讨论一下如何将二进制形式的浮点数放入内存中。

原则上讲,上面的科学计数法公式中,符号 sign、尾数 mantissa、基数 base 和指数 exponent 都是不确定因素,都需要在内存中体现出来。但是现在基数 base 已经确定是二进制了,就不用在内存中体现出来了,这样只需要在内存中存储符号 sign、尾数 mantissa、指数 exponent 这三个不确定的元素就可以了。

仍然以 19.625 为例,将它转换成二进制形式的浮点数格式:

19.625 = 1.0011101×24

此时符号 sign 为 0,尾数 mantissa 为 1.0011101,指数 exponent 为 4。

1) 符号的存储

符号的存储很容易,就像存储 short、int 等普通整数一样,单独分配出一个位(Bit)来,用 0 表示正数,用 1 表示负数。对于 19.625,这一位的值是 0。

2) 尾数的存储

当采用二进制形式后,尾数部分的取值范围为 1 ≤ mantissa < 2,这意味着:尾数的整数部分一定为 1,是一个恒定的值,这样就无需在内存中提现出来,可以将其直接截掉,只要把小数点后面的二进制数字放入内存中即可。对于 1.0011101,就是把 0011101 放入内存。

我们不妨将真实的尾数命名为 mantissa,将内存中存储的尾数命名为 mant,那么它们之间的关系为:

mantissa = 1.mant


如果 base 采用其它进制,那么尾数的整数部分就不是固定的,它有多种取值的可能,以十进制为例,尾数的整数部分可能是 1~9 之间的任何一个值,这样一来尾数的整数部分就不能省略了,必须在内存中体现出来。而将 base 设置为二进制就可以节省掉一个位(Bit)的内存,这也算是采用二进制的一点点优势。

3) 指数的存储

指数是一个整数,并且有正负之分,不但需要存储它的值,还得能区分出正负号来。

short、int、long 等类型的整数在内存中的存储采用的是补码加符号位的形式,数值在写入内存之前必须先进行转换,读取以后还要再转换一次。但是为了提高效率,避免繁琐的转换,指数的存储并没有采用补码加符号位的形式,而是设计了一套巧妙的解决方案,稍等我会为您解开谜团。

为二进制浮点数分配内存

C语言中常用的浮点数类型为 float 和 double;float 始终占用 4 个字节,double 始终占用 8 个字节。

下图演示了 float 和 double 的存储格式:

浮点数的内存被分成了三部分,分别用来存储符号 sign、尾数 mantissa 和指数 exponent ,当浮点数的类型确定后,每一部分的位数就是固定的。

符号 sign 可以不加修改直接放入内存中,尾数 mantissa 只需要将小数部分放入内存中,最让人疑惑的是指数 exponent 如何放入内存中,这也是我们在前面留下的一个谜团,下面我们以 float 为例来揭开谜底。

float 的指数部分占用 8 Bits,能表示从 0~255 的值,取其中间值 127,指数在写入内存前先加上127,读取时再减去127,正数负数就显而易见了。19.625 转换后的指数为 4,4+127 = 131,131 换算成二进制为 1000 0011,这就是 19.626 的指数部分在 float 中的最终存储形式。

先确定内存中指数部分的取值范围,得到一个中间值,写入指数时加上这个中间值,读取指数时减去这个中间值,这样符号和值就都能确定下来了。

中间值的求取有固定的公式。设中间值为 median,指数部分占用的内存为 n 位,那么中间值为:

median = 2n-1 - 1

对于 float,中间值为 28-1 - 1 = 127;对于 double,中间值为 211-1 -1 = 1023。

我们不妨将真实的指数命名为 exponent,将内存中存储的指数命名为 exp,那么它们之间的关系为:

exponent = exp - median

也可以写作:

exp = exponent + median

为了方便后续文章的编写,这里我强调一下命名:
  • mantissa 表示真实的尾数,包括整数部分和小数部分;mant 表示内存中存储的尾数,只有小数部分,省略了整数部分。
  • exponent 表示真实的指数,exp 表示内存中存储的指数,exponent 和 exp 并不相等,exponent 加上中间数 median 才等于 exp。

用代码验证 float 的存储

19.625 转换成二进制的指数形式为:

19.625 = 1.0011101×24

此时符号为 0;尾数为 1.0011101,截掉整数部分后为 0011101,补齐到 23 Bits 后为 001 1101 0000 0000 0000 0000;指数为 4,4+127 = 131,131 换算成二进制为 1000 0011。

综上所述,float 类型的 19.625 在内存中的值为:0 - 10000011 - 001 1101 0000 0000 0000 0000。

下面我们通过代码来验证一下:

 
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3.  
  4. //浮点数结构体
  5. typedef struct {
  6. unsigned int nMant : 23; //尾数部分
  7. unsigned int nExp : 8; //指数部分
  8. unsigned int nSign : 1; //符号位
  9. } FP_SINGLE;
  10.  
  11. int main()
  12. {
  13. char strBin[33] = { 0 };
  14. float f = 19.625;
  15. FP_SINGLE *p = (FP_SINGLE*)&f;
  16.  
  17. itoa(p->nSign, strBin, 2);
  18. printf("sign: %s\n", strBin);
  19. itoa(p->nExp, strBin, 2);
  20. printf("exp: %s\n", strBin);
  21. itoa(p->nMant, strBin, 2);
  22. printf("mant: %s\n", strBin);
  23.  
  24. return 0;
  25. }
运行结果:
sign: 0
exp: 10000011
mant: 111010000000000000000

mant 的位数不足,在前面补齐两个 0 即可。
printf() 不能直接输出二进制形式,这里我们借助 itoa() 函数将十进制数转换成二进制的字符串,再使用%s输出。itoa() 虽然不是标准函数,但是大部分编译器都支持。不过 itoa() 在 C99 标准中已经被指定为不可用函数,在一些严格遵循 C99 标准的编译器下会失效,甚至会引发错误,例如在 Xcode(使用 LLVM 编译器)下就会编译失败。如果 itoa() 无效,请使用%X输出十六进制形式,十六进制能够很方便地转换成二进制。

精度问题

对于十进制小数,整数部分转换成二进制使用“展除法”(就是不断除以 2,直到余数为 0),一个有限位数的整数一定能转换成有限位数的二进制。但是小数部分就不一定了,小数部分转换成二进制使用“乘二取整法”(就是不断乘以 2,直到小数部分为 0),一个有限位数的小数并不一定能转换成有限位数的二进制,只有末位是 5 的小数才有可能转换成有限位数的二进制,其它的小数都不行。 

float 和 double 的尾数部分是有限的,固然不能容纳无限的二进制;即使小数能够转换成有限的二进制,也有可能会超出尾数部分的长度,此时也不能容纳。这样就必须“四舍五入”,将多余的二进制“处理掉”,只保留有效长度的二进制,这就涉及到了精度的问题。也就是说,浮点数不一定能保存真实的小数,很有可能保存的是一个近似值。

对于 float,尾数部分有 23 位,再加上一个隐含的整数 1,一共是 24 位。最后一位可能是精确数字,也可能是近似数字(由四舍五入、向零舍入等不同方式得到);除此以外,剩余的23位都是精确数字。从二进制的角度看,这种浮点格式的小数,最多有 24 位有效数字,但是能保证的是 23 位;也就是说,整体的精度为 23~24 位。如果转换成十进制,224 = 16 777 216,一共8位;也就是说,最多有 8 位有效数字,但是能保证的是 7 位,从而得出整体精度为 7~8 位。

对于 double,同理可得,二进制形式的精度为 52~53 位,十进制形式的精度为 15~16 位。

IEEE 754 标准

浮点数的存储以及加减乘除运算是一个比较复杂的问题,很多小的处理器在硬件指令方面甚至不支持浮点运算,其他的则需要一个独立的协处理器来处理这种运算,只有最复杂的处理器才会在硬件指令集中支持浮点运算。省略浮点运算,可以将处理器的复杂度减半!如果硬件不支持浮点运算,那么只能通过软件来实现,代价就是需要容忍不良的性能。

PC 和智能手机上的处理器就是最复杂的处理器了,它们都能很好地支持浮点运算。

在六七十年代,计算机界对浮点数的处理比较混乱,各家厂商都有自己的一套规则,缺少统一的业界标准,这给数据交换、计算机协同工作带来了很大不便。

作为处理器行业的老大,Intel 早就意识到了这个问题,并打算一统浮点数的世界。Intel 在研发 8087 浮点数协处理器时,聘请到加州大学伯克利分校的 William Kahan 教授(最优秀的数值分析专家之一)以及他的两个伙伴,来为 8087 协处理器设计浮点数格式,他们的工作完成地如此出色,设计的浮点数格式具有足够的合理性和先进性,被 IEEE 组织采用为浮点数的业界标准,并于 1985 年正式发布,这就是 IEEE 754 标准,它等同于国际标准 ISO/IEC/IEEE 60559。

IEEE 是 Institute of Electrical and Electronics Engineers 的简写,中文意思是“电气和电子工程师协会”。

IEEE 754 简直是天才一般的设计,William Kahan 教授也因此获得了 1987 年的图灵奖。图灵奖是计算机界的“诺贝尔奖”。

目前,几乎所有的计算机都支持 IEEE 754 标准,大大改善了科学应用程序的可移植性,C语言编译器在实现浮点数时也采用了该标准。

不过,IEEE 754 标准的出现晚于C语言标准(最早的 ANSI C 标准于 1983 年发布),C语言标准并没有强制编译器采用 IEEE 754 格式,只是说要使用科学计数法的形式来表示浮点数,但是编译器在实现浮点数时,都采用了 IEEE 754 格式,这既符合C语言标准,又符合 IEEE 标准,何乐而不为。

特殊值

IEEE 754 标准规定,当指数 exp 的所有位都为 1 时,不再作为“正常”的浮点数对待,而是作为特殊值处理:
  • 如果此时尾数 mant 的二进制位都为 0,则表示无穷大:
    • 如果符号 sign 为 1,则表示负无穷大;
    • 如果符号 sign 为 0,则表示正无穷大。
  • 如果此时尾数 mant 的二进制位不全为 0,则表示 NaN(Not a Number),也即这是一个无效的数字,或者该数字未经初始化。

非规格化浮点数

当指数 exp 的所有二进制位都为 0 时,情况也比较特殊。

对于“正常”的浮点数,尾数 mant 隐含的整数部分为 1,并且在读取浮点数时,内存中的指数 exp 要减去中间值 median 才能还原真实的指数 exponent,也即:

mantissa = 1.mant
exponent = exp - median


但是当指数 exp 的所有二进制位都为 0 时,一切都变了!尾数 mant 隐含的整数部分变成了 0,并且用 1 减去内存中的指数 exp 才能还原真实的指数 exponent,也即:

mantissa = 0.mant
exponent = 1 - exp

对于 float,exponent = 1 - 127 = -126,指数 exponent 的值恒为 -126;对于 double,exponent = 1 - 1023 = -1022,指数 exponent 的值恒为 -1022。

当指数 exp 的所有二进制位都是 0 时,我们将这样的浮点数称为“非规格化浮点数”;当指数 exp 的所有二进制位既不全为 0 也不全为 1 时,我们称之为“规格化浮点数”;当指数 exp 的所有二进制位都是 1 时,作为特殊值对待。 也就是说,究竟是规格化浮点数,还是非规格化浮点数,还是特殊值,完全看指数 exp。

+0 和 -0 的表示

对于非规格化浮点数,当尾数 mant 的所有二进制位都为 0 时,整个浮点数的值就为 0:
  • 如果符号 sign 为 0,则表示 +0;
  • 如果符号 sign 为 1,则表示 -0。

IEEE 754 为什么增加非规格化浮点数

我们以 float 类型为例来说明。

对于规格化浮点数,当尾数 mant 的所有位都为 0、指数 exp 的最低位为 1 时,浮点数的绝对值最小(符号 sign 的取值不影响绝对值),为 1.0 × 2-126,也即 2-126

对于一般的计算,这个值已经很小了,非常接近 0 值了,但是对于科学计算,它或许还不够小,距离 0 值还不够近,非规格化浮点数就是来弥补这一缺点的:非规格化浮点数可以让最小值更小,更加接近 0 值。

对于非规格化浮点数,当尾数的最低位为 1 时,浮点数的绝对值最小,为 2-23 × 2-126 = 2-149,这个值比 2-126 小了 23 个数量级,更加即接近 0 值。

让我更加惊讶的是,规格化浮点数能够很平滑地过度到非规格化浮点数,它们之间不存在“断层”,下表能够让读者看得更加直观。
说明 float 内存 exp exponent mant mantissa 浮点数的值 flt
0值
最小非规格化数





最大非规格化数
0 - 00...00 - 00...00
0 - 00...00 - 00...01
0 - 00...00 - 00...10
0 - 00...00 - 00...11
……

0 - 00...00 - 11...10
0 - 00...00 - 11...11
0
0
0
0
……

0
0
-126
-126
-126
-126
……

-126
-126
0
2^-23
2^-22
1.1 × 2^-22
……

0.11...10
0.11...11
0
2^-23
2^-22
1.1 × 2^-22
……

0.11...10
0.11...11
+0
2^-149
2^-148
1.1 × 2^-148
……

1.11...10 × 2^-127
1.11...11 × 2^-127
最小规格化数






最大规格化数
0 - 00...01 - 00...00
0 - 00...01 - 00...01
……
0 - 00...10 - 00...00
0 - 00...10 - 00...01
……
0 - 11...10 - 11...10
0 - 11...10 - 11...11
1
1
……
2
2
……
254
254
-126
-126
……
-125
-125

127
127
0.0
0.1
……
0.0
0.1
……
0.11...10
0.11...11
1.0
1.1
……
1.0
1.1
……
1.11...10
0.11...11
1.0 × 2^-126
1.1 × 2^-126
……
1.0 × 2^-125
1.1 × 2^-125
……
1.11...10 × 2^127
1.11...11 × 2^127
  0 - 11...11 - 00...00 - - - - +∞
  0 - 11...11 - 00...01
……
0 - 11...11 - 11...11
- - - - NaN
^ 表示次方,例如 2^10 表示 2 的 10 次方。
上表演示了正数时的情形,负数与此类似。请读者注意观察最大非规格化数和最小规格化数,它们是连在一起的,是平滑过渡的。

舍入模式

浮点数的尾数部分 mant 所包含的二进制位有限,不可能表示太长的数字,如果尾数部分过长,在放入内存时就必须将多余的位丢掉,取一个近似值。究竟该如何来取这个近似值,IEEE 754 列出了四种不同的舍入模式。

1) 舍入到最接近的值

就是将结果舍入为最接近且可以表示的值,这是默认的舍入模式。最近舍入模式和我们平时所见的“四舍五入”非常类似,但有一个细节不同。

对于最近舍入模式,IEEE 754 规定,当有两个最接近的可表示的值时首选“偶数”值;而对于四舍五入模式,当有两个最接近的可表示的值时要选较大的值。以十进制为例,就是对.5的舍入上采用偶数的方式,请看下面的例子。

最近舍入模式:Round(0.5) = 0、Round(1.5) = 2、Round(2.5) = 2
四舍五入模式:Round(0.5) = 1、Round(1.5) = 2、Round(2.5) = 3

2) 向 +∞ 方向舍入(向上舍入)

会将结果朝正无穷大的方向舍入。标准库函数 ceil() 使用的就是这种舍入模式,例如,ceil(1.324) = 2,Ceil(-1.324) = -1。

3) 向 -∞ 方向舍入(向下舍入)

会将结果朝负无穷大的方向舍入。标准库函数 floor() 使用的就是这种舍入模式,例如,floor(1.324) = 1,floor(-1.324) = -2。

4) 向 0 舍入(直接截断)

会将结果朝接近 0 的方向舍入,也就是将多余的位数直接丢掉。C语言中的类型转换使用的就是这种舍入模式,例如,(int)1.324 = 1,(int) -1.324 = -1。

总结

与定点数相比,浮点数在精度方面损失不小,但是在取值范围方面增大很多。牺牲精度,换来取值范围,这就是浮点数的整体思想。

IEEE 754 标准其实还规定了浮点数的加减乘除运算,不过本文的重点是讲解浮点数的存储,所以对于浮点数的运算不再展开讨论。

答疑解惑

上节我们还留下了一个疑问,就是用 %f 输出 128.101 时得到的是一个近似值,而不是一个精确值,这是因为,128.101 转换为浮点格式后,尾数部分过长,被丢掉了,不能“真实”地存储了。

128.101 转换成二进制为:

10000000.0001100111011011001000101101……(无限循环)

向左移动 7 位后为:

1.00000000001100111011011001000101101……

由此可见,尾数部分为:

000 0000 0001 1001 1101 1011 001000101101……

将多出的二进制丢掉后为:

000 0000 0001 1001 1101 1011

使用 printf 输出时,还需要进行还原,还原后的二进制为:

10000000.0001100111011011

转换成十进制为 128.1009979248046875,按照四舍五入的原则取 6 位小数,就是128.100998。

From: http://c.biancheng.net/cpp/html/3099.html

Views: 31 | Added by: liangcx126 | Rating: 1.0/100
Total comments: 0
avatar