前天迫于摸鱼,在leetcode做到了道题目,略有吐槽和体会,题目如下:

给定两个以字符串形式表示的非负整数 num1 和 num2,返回 num1 和 num2 的乘积,它们的乘积也表示为字符串形式。

示例 1:

输入: num1 = "2", num2 = "3"

输出: "6"

示例 2:

输入: num1 = "123", num2 = "456"

输出: "56088"

说明:

1,num1 和 num2 的长度小于110。

2,num1 和 num2 只包含数字 0-9。

3,num1 和 num2 均不以零开头,除非是数字 0 本身。

4,不能使用任何标准库的大数类型(比如 BigInteger)或直接将输入转换为整数来处理。

题目链接:https://leetcode-cn.com/problems/multiply-strings/

先说结论,这题用JavaScript解答是深坑…..,而且你是跑不过最大的用例的,因为JavaScript精度存储机制就是如此。

首先,这个题目标注难度为中等,他需要你不是用直接转换数字进行相乘的方法得出,这里需要了解一个知识点,JavaScript位移计算,实际上我从对它不熟悉到理解使用看的不是JavaScript方面的介绍,而是这个https://www.cnblogs.com/outerspace/p/10846106.html,说到这里,大坑就是计算的结果,因为我上面说过坑的原因,即使你真的直接相乘,你可以在console或者node中试一下。

987654321 * 123456789

你大概会得到"121932631112635260",但是你肯定发现不对,这个相乘尾数不可能是0的,这里就会碰到JavaScript计算精度的坑了,以下部分学术型理论,可以战术跳过直接看下划线结论。

计算机的二进制实现和位数限制有些数无法有限表示。就像一些无理数不能有限表示,如 圆周率 3.1415926…,10 / 3 = 3.3333... 等。JavaScript 遵循 IEEE 754 规范,采用双精度存储(double precision),占用 64 bit。

根据按照 IEEE 754这个规范可找到说明:

IEEE 754 double-precision binary floating-point format: binary64[edit]

Double-precision binary floating-point is a commonly used format on PCs, due to its wider range over single-precision floating point, in spite of its performance and bandwidth cost. As with single-precision floating-point format, it lacks precision on integer numbers when compared with an integer format of the same size. It is commonly known simply as double. The IEEE 754 standard specifies a binary64 as having:

  • Sign bit: 1 bit // 符号位:1位
  • Exponent: 11 bits // 指数:11位
  • Significand precision: 53 bits (52 explicitly stored) // 有效精度:53位(显式存储52位)

那么按照这个换算,浮点数就没办法四舍五入表示了,总不能显示几百+的位数吧,这时候这时候浮点数只能模仿十进制进行四舍五入了,但是二进制只有 0 和 1 两个,于是变为 0 舍 1 入。这就是计算机中部分浮点数运算时出现误差,丢失精度的原因。

大整数的精度丢失和浮点数本质上是一样的,根据规范"显式存储52位", JS 中能精准表示的最大整数是 Math.pow(2, 53),即 9007199254740992。大于 9007199254740992 的可能会丢失精度。

你可以对其进行四则运算测试一下,得出结果非常不稳定,所以如果非要进行这种运算,建议进行分段拆分。

这道题主要让我了解到位移运算和JavaScript极限情况下计算精度的问题,当然基于现在的编译器已经优化过乘法计算,所以你真的按照位移去算出结果,代码维护性和性能也并不是最佳的,但是这其中涉及到的计算机基础知识对于理解很多JavaScript计算方面怪异表现有一定的帮助。

参考资料:

https://stackoverflow.com/questions/2373791/bitshift-in-javascript

https://en.wikipedia.org/wiki/Double-precision_floating-point_format

preView