阅读 897531

二进制数字存储(二进制数字存储器实现原理)

二进制数字存储

二进制整数存储概念快速复习

原码

一个 8 位的存储单元可以存储 0000000011111111256 种数字,真值(即真实数值,用10进制表示)从 0255。为了引入负数,所以设计出了原码:用存储单元的第一位表示符号,1 位负,0 为正,后面的位表示真值的绝对值。同样以 8 位存储单元位例,在用原码的方式下我们依然可以表示 256 个数,从 1111111101111111,真值范围为 -127127,可能你发现真值一共只有255 个,因为 1000000000000000 表示的都是 0,即-0+0

反码

由于原码中,+x-x使用二进制加法(利用加法电路)相加不能等于0,设计了反码,即:如果是正数则保持不变,如果是负数,则除符号位之外按位取反。这样正负2数相加就变成了 11111111 ,也就是-0,注意这里的结果也是反码。

补码

补码的定义就是正数和 0 的补码就是原码,负数的补码是其反码 +1-1 的原码是 10000001,反码是 11111110,补码在反码的基础上 +1,即为 11111111-0 取补码后跟 0 是一致的,没有了两个 0 的问题,没了-0后多出的10000000表示-128,真值数也变回了256。这也就是我们今天计算机所用的存储和计算的方式

由于高位溢出舍弃,采用补码的方式,无论是从11111111(-1)00000000(0),还是从01111111(127)100000000(-128)都是连续的,所有数其实是一个类似钟表上数字的闭合的环。0是0点位置,-128是6点位置。反码、补码,通过数学上的同余定理中的同余式相加,达到了用加法来实现减法的效果。进一步理解中间的巧妙可阅读补码的工作原理以及同余。

JavaScript的数字存储

有人可能意识到了什么,上面的补码去掉了-0,可JavaScript中又确实存在-0,怎么回事?对于C、C++、JAVA等这类强类型语言,内部整数和小数的存储实现是分开的,而JavaScript并没有实现上述整数的逻辑,其整数和小数,都是采用IEEE754 标准,使用浮点数的方式存储的。

二进制小数的表示

如何用二进制来表示小数?曾经我以为,只要在整数的基础上,再使用另一个字节来表示小数位就行了,比如3的二进制是111,那0.03可以是111 000010,后面的000010表示小数为2位。后来明白这个想当然的方案虽然可以存储,却无法用于运算,没有真正理解进制的意义。

以十进制小数123.45为例,其十进制的本质是

1×102+2×101+3×100+4×10−1+5×10−21×10^2 + 2×10^1+3×10^0+4×10^{-1}+5×10^{-2}1×102+2×101+3×100+4×101+5×102

对其他进制也引入小数点,如果123.45是个8进制的数,转换为十进制应该是

1×82+2×81+3×80+4×8−1+5×8−2=83.5781251×8^2 + 2×8^1+3×8^0+4×8^{-1}+5×8^{-2} = 83.5781251×82+2×81+3×80+4×81+5×82=83.578125

对应二进制数101.11,转为为十进制应该是

1×22+1×21+1×20+1×2−1+1×2−2=5.751×2^2 + 1×2^1+1×2^0+1×2^{-1}+1×2^{-2} = 5.751×22+1×21+1×20+1×21+1×22=5.75

十进制小数123.45可以用科学计数法表示为

1.2345×1021.2345×10^21.2345×102

同理二进制数101.11也可以用科学计数法表示为

1.0111×221.0111×2^21.0111×22

如果指数部分也用二进制表示,那就是

1.0111×2101.0111×2^{10}1.0111×210

由于表示进制的底数2是恒定,这里关键的数字是基数1.0111和指数10,当然还有一个隐藏的符号+来表示是正数

IEEE754 标准

IEEE754 标准是二进制浮点数运算标准,规定了计算机中的二进制浮点数的存储和计算的标准。这是一个针对CPU与浮点运算器等硬件底层的标准,因此在采用此标准的硬件基础上运行的JavaScript也遵从这一标准。

数据组成

该标准规定,浮点数有的三个组成部分,从左到右依次是:

符号位(sign),指数偏移值(exponent)和分数值(fraction)。

最高有效位被指定为符号位(sign);“指数部分”,即次高有效的e个比特,存储指数部分;最后剩下的f个低有效位的比特,存储“有效数”(significand)的小数部分。这里注意整数部分是不存储的,因为其在规约形式下一定是1,非规约形式下一定是0。这部分之后会再说明。

以上面二进制数1.0111×221.0111×2^{2}1.0111×22为例,符号位0表示正数,指数部分是10,分数值存储小数部分0111

具体的位数,根据精度又分为两种,单精度和双精度:

  • 单精度:符号位 1bit,指数偏移值 8bit,分数值 23bit,共 32bit

  • 双精度:符号位 1bit,指数偏移值 11bit,分数值 52bit,共 64bit

由于当前版本的chrome都是双精度实现,下面都以双精度来说明。

指数偏移值

指数偏移值(exponent bias),即浮点数表示法中指数域的编码值,等于指数的实际值加上某个固定的值,IEEE 754标准规定该固定值为2e−1−12^{e-1}-12e1−1,其中的e为存储指数的比特的长度。

对于双精度,它的指数域是11个比特,固定偏移值是211−1−1=10232^{11-1}-1 = 10232111−1=1023(从二进制角度看就是次高位+1,最低位-1)。11位无符号的范围是0~2047, 由于0和2047用作特殊值处理,正常使用范围是1~2046,所以去掉固定偏移值后,指数部分实际取值是从-1022到1023。1.0111×221.0111×2^{2}1.0111×22指数实际值为2,指数域编码值为2 + 1023 = 1025。

加上偏移值,好处是可以用长度为e个比特的无符号整数来表示所有的指数取值,这使得两个浮点数的指数大小的比较更为容易,可以按照字典次序比较两个浮点表示的大小。这种移码表示的指数部分,称作阶码。

规约形式的浮点数

如果浮点数中指数部分满足 1≤exponent≤2e−21≤ exponent ≤ 2^e - 21≤exponent≤2e−2 ,也就是上面提到的正常使用范围1~2046,且在科学计数法的表示方式下,分数 (fraction) 部分最高有效位(即整数字)是1,那么这个浮点数将被称为规约形式的浮点数。由于整数部分永远是1,所以这个1是不存储的。

非规约形式的浮点数

如果浮点数的指数部分的编码值是0,分数部分非零,那么这个浮点数将被称为非规约形式的浮点数。非规约形式的浮点数的指数偏移值比规约形式的浮点数的指数偏移值小1。

当某个数字相当接近零时,比如 1×2−10231 × 2^{-1023}1×21023 ,其指数部分超过双精度最小值-1022,如果增大指数,又会使分数的整数部分不为1。非规约形式的浮点数就用来表示这种相当接近零的数,将数字该写成 0.1×2−10220.1 × 2^{-1022}0.1×21022,此时指数部分的编码值是0(此时偏移值是1022),小数部分是1。

为什么偏移值要小1?因为规约形式的浮点数舍弃了整数部分1这位数,如果不调整,无法保证有效数是整数部分一定是0,引发记数逻辑混乱。

特殊值

最后指出三个特殊值:

  • 如果指数是0并且尾数的小数部分是0,这个数就是±0(和符号位相关)

  • 如果指数 = 2e−12^e-12e−1(双精度时2047),并且尾数的小数部分是0,这个数是±Infinity(同样和符号位相关)

  • 如果指数 = 2e−12^e-12e−1(双精度时2047),并且尾数的小数部分非0,这个数表示为非数(NaN,和符号位无关)。

虽然 +0 === -0 返回true,但两者实际存储的数据是不同的
±Infinity、 NaN本质是浮点数,所以typeof ±Infinitytypeof NaN返回值都是number
想一想为什么规定 Infinity === Infinity 返回true+0 === -0 返回true,而 NaN === NaN 返回false
NaN浪费了大量的编码空间,相比同样位数的整数型,虽然总的信息量是一样的,但浮点型所能表达有效数据更少

总结如下:

形式指数分数部分
00
非规约形式0大于0
规约形式1到 2e−22^e - 22e−2大于等于0
无穷2e−12^e - 12e−10
NaN2e−12^e - 12e−1非0

双精度浮点数各种极值情况:

类别正负号实际指数偏移指数指数域尾数域(52位)数值(正负都有仅展示正)
0-10230000 0000 00000000 …… 00000.0
负零1-10230000 0000 00000000 …… 0000−0.0
1001023011 1111 11110000 …… 00001.0
-1101023011 1111 11110000 …… 0000−1.0
绝对值最小的非规约数0/1-10220000 0000 00000000 …… 00012−52×2−1022=2−1074≈5×10−3242^{-52} × 2^{-1022} = 2^{-1074} ≈ 5×10^{-324}252×21022=21074≈5×10324
Number.MIN_VALUE
这个数再除以2就是0了
绝对值最大的非规约数0/1-10220000 0000 00001111……1111(1−2−52)×2−1022≈2.225×10−308(1−2^{-52}) × 2^{-1022} ≈ 2.225×10^{-308}(1−252)×21022≈2.225×10308
绝对值最小的规约数0/1-10221000 0000 00010000 …… 00002−1022≈2.225×10−3082^{-1022} ≈ 2.225×10^{-308}21022≈2.225×10308
和上面的相差最小非规约数
绝对值最大的规约数0/110232046111 1111 11101111……111121024−2−52×210232^{1024} - 2^{-52} × 2^{1023}21024−252×21023
Number.MAX_VALUE
使用bigint 2n ** 1024n - 2n ** 971n验证
绝对值最大精确整数
满足n±1都不等于n
0/1521075100 0011 00111111……1111253−12^{53} - 1253−1
Number.MAX_SAFE_INTEGER
使用2 ** 53 - 1验证
正无穷010242047111 1111 11110000 …… 0000+Infinity
负无穷110242047111 1111 11110000 …… 0000−Infinity
NaN0/110242047111 1111 1111非全0NaN

Number.MIN_VALUE是正数,Number.MIN_SAFE_INTEGER ==== - Number.MAX_SAFE_INTEGER,是负数

浮点数的舍入

任何有效数上的运算结果,通常都存放在较长的寄存器中,当结果被放回浮点格式时,必须将多出来的比特丢弃。IEEE标准列出4种不同的方法,经过研究发现应该采用的是舍入到最接近原则:优先舍入到最接近,在一样接近的情况下偶数优先(在二进制中最后一位是0)。

若舍入位是0,舍弃;若舍入位是1,且其不是最后一位就进位,否则采用偶数优先原则

例子:

2**53 + 1,0.1被舍弃(在指数对齐后,1在尾数域第53位,超过存储范围);2**53 + 2,无需舍入;2**53 + 3,尾数1.1进位为10;2**53 + 4 ,无需舍入;2**53 + 5,尾数10.1舍弃为10

再以1/3为例,转换位2进制位为 0.010101……,经过存储后为0.0101……01,小数点后54位(53位有小数),之后数都被舍弃,转换回10进制,根据等比公式可得结果为

(1 - 2 ** -54) /3 = 0.333333333333333314829616256247390992939472198486328125,可以看到小数点有效位数为只能到16位,到第17位时已经从不正确了,计算机内部进行了舍弃。

再将16位的0.3333333333333333转换位2进制,可以发现,保留小数点54位时,和1/3是一样的。也就是说16位的0.3…3和1/3没用区别。如果是15位的0.3…转换54位二进制,最后几位是01001111,出现差异。

再进一步,将16位的0.3…3 * 3,想一想结果是什么,会变成0.9…9吗?

结果1,存储不了的最后一位1会按照偶数优先原则进位。

那舍入会引入什么问题呢?

浮点数的精度

上例1/3,为什么小数点有效位数,也就是精度为只能到16位?显然决定精度的是尾数域 。对于规约数而言,其存储的有效位数是尾数域52位外加省略的整数位1位一共53位,其精度为2^53=9007199254740992,它的长度是 16。在大多数情况精度是16位,但因为不是满999的16位,导致有一小部分数,比如0.9007199254740999,精度只有15位。如果是非规约数,精度会比规约数低,并且越接近0,尾数域利用率越低,精度也越低,最低就只有1位了(如Number.MIN_VALUE)了。

舍入后精度丢失引发的一些问题

为什么0.1 + 0.2 !== 0.3,0.1 + 0.3 === 0.4?

0.1 存储的二进制为                0.0001 1001 1001 1001 1001 1001 1001 1001 1001 1001 1001 1001 1001 101 (101比100更接近1001 1) 0.2 存储的二进制为                0.0011 0011 0011 0011 0011 0011 0011 0011 0011 0011 0011 0011 0011 01  (01比00更接近0011) 结果是                           0.0100 1100 1100 1100 1100 1100 1100 1100 1100 1100 1100 1100 1100 111 最后一位1存储不了,偶数优先原则进位 0.0100 1100 1100 1100 1100 1100 1100 1100 1100 1100 1100 1100 1101 00 而实际0.3 二进制为                0.0100 1100 1100 1100 1100 1100 1100 1100 1100 1100 1100 1100 1100 11 复制代码

可以发现首先0.1、0.2在存储时都进行了进位,导致相加后再次进位。而0.3在存储时进行了舍弃,一入一舍造成两者差了最后1位的1,也就是2−542^{-54}254

两者转换为十进制分别为 0.3000000000000000444089209850062616169452667236328125

和 0.299999999999999988897769753748434595763683319091796875

显然下面的更接近0.3。其实从16位精度考虑,两者都应该是0.3,但又不能让内存不一样的2个数相等,所以前者被舍入为0.30000000000000004。位数达到17,超过精度长度16,也说明了这个数产生了误差。

单精度浮点数时, 0.1 + 0.2 === 0.3 成立,JavaScript中可以用下面代码验算,具体过程请自行研究

const fa1 = new Float32Array([0.1, 0.2]) const fa2 = new Float32Array([fa1[0] + fa1[1], 0.3]) fa2[0] === fa2[1] // true 复制代码

再看第二个等式

0.1 + 0.3 二进制为               0.0110 0110 0110 0110 0110 0110 0110 0110 0110 0110 0110 0110 0110 011 最后一位1存储不了,偶数优先原则进位 0.0110 0110 0110 0110 0110 0110 0110 0110 0110 0110 0110 0110 0110 10 复制代码

而0.4转换为二进制也是这串数字,所以两者是相等的。

0.1 * 3 !== 0.3

由于乘法的本质就是加法,所以乘法同样存在舍入误差。标题的0.1*3,对于二进制而言,3转换为11,背后就是0.1+0.2。乘以10的整数倍同样不能幸免,比如0.07*100 = 7.000000000000001,100会转换为64+32+4的形式计算。

es6引入了Number.EPSILON以便安全地比较浮点数,在没用特别精确要求的前提下,如果两个数之间差值小于Number.EPSILON,就可以认为两者是相等的,Number.EPSILON大小其实就是2−522^{-52}252,也就是当实际指数为0时,尾数域最后一位的大小。显然这是个推荐的值,特殊场景下可以按照实际需求自己定义安全比较的范围。也采用Number.prototype.toPrecision来自定义精度范围

使用toPrecisiontoFixed舍入存在的问题

toPrecisiontoFixed都能用来做四舍五入,但当舍入位是5时,可能得不到想要的结果,比如

0.15.toFixed(1) = 0.1

这是因为0.15存储为二进制,再转换为十进制为0.1499999999999999944488848768742172978818416595459,真实的舍入位是4。

解决的办法是给这个数的尾数域  +1 ,再调用toPrecisiontoFixed

在这个例子中,要计算尾数域 +1的值,先将0.15转换位2进制得 0.001001 1001 ...,科学计数法指数是-3,再减去尾数域长度52得-55,最终算得值为 2−552^{-55}255(0.15 + 2**-55).toFixed(1) = 0.2

当然精度问题也可以借助第三方工具解决

lodash.round源码分析

lodash.round方法可以代替toFixed 实现指定小数位数的四舍五入,下面是其核心源码

function lodashRound(number, precision) {     // 处理可能是1.5e-7这种指数形式数据     var pair = (number + 'e').split('e');     // 将原数据右移小数点放大方后,调用Math.round四舍五入     // 这里的放大其实是输入了一个新的数     var value = Math.round(pair[0] + 'e' + (+pair[1] + precision));      pair = (value + 'e').split('e');     // 变回原来的大小     return +(pair[0] + 'e' + (+pair[1] - precision)); } 复制代码

+(num + 'en')  这种形式可以快速移动小数点位数,其中n为要移动的位数。如0.07*100可以通过+(0.07+ 'e2')来计算
这种将小数先无损放大到整数,计算后再缩小,是很多库进行精确计算的方式。尝试用这个方法算0.1+0.2
但是lodash.addlodash.multiply调用的是原生加法和乘法,无法解决精度误差

big.js源码分析

big.js提供了更多的精确数字操作方法,它的思路是采用人类十进制的视角来处理,下面以加法plus的核心代码为例

// 原pluse是Big类原型上的方法,这个为方便展示改为函数形式 // big.js根据数字创建Big类的对象来实现各种计算,这里 x、y 都是Big类的对象。 // 对象属性说明,以123.456为例 // class Big { //  readonly c: number[] | null;  值的系数数组,例子为 [1,2,3,4,5,6] //  readonly e: number | null;    值的10为底指数, 例子为2 //  readonly s: number | null;    值的符号,取值1或-1, 例子为1 // } function plus (x, y) {      var e, k, xc = x.c, xe = x.e, yc = y.c            /** 这里省略符号不同调用减法,以及确保x、y都不是0的代码  **/            // 使两边的指数相等,指数小的一方数组前面补0      // Note: reverse faster than unshifts.      if (e = xe - ye) {       if (e > 0) {         ye = xe;         t = yc;       } else {         e = -e;         t = xc;       }       t.reverse();       for (; e--;) t.push(0);       t.reverse();     }     // Point xc to the longer array.     if (xc.length - yc.length < 0) {       t = yc;       yc = xc;       xc = t;     }      // 十进制加法实现,k为进位      for (k = 0, e = yc.length; e; xc[e] %= 10) {          xc[--e] = xc[e] + yc[e] + k          // 位运算 | 会将小数转换为有符号的32位整型,这里 | 0 就是取整。          // ps: | 0 和 Math.trunc有什么区别?谁快?          k = xc[e] / 10 | 0      }     if (k) {       xc.unshift(k);       ++ye;     }     // 去掉尾部的0     for (e = xc.length; xc[--e] === 0;) xc.pop();     y.c = xc;     y.e = ye;     return y.toNumber(); } 复制代码

其乘法times ,舍入round、toFixed都是类似的思路。big.js本身是为解决大精度数据计算设计的。借助核心属性系数数组,big.js转小数为数组,可以实现非常高精度的计算,当然性能上肯定比不上可以调用cpu指令集的原生方法。

同位数的浮点型和整数型存储比较

  • 浮点型能表达小数,整数型只能表达整数

  • 信息量利用上,浮点型不如整数型

  • 浮点型表达范围更大,但整数型精度更高,且运算速度更快


作者:桂之風
链接:https://juejin.cn/post/7028866557480534046


文章分类
代码人生
文章标签
版权声明:本站是系统测试站点,无实际运营。本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容, 请发送邮件至 XXXXXXo@163.com 举报,一经查实,本站将立刻删除。
相关推荐