JavaScript大数相加相乘实现

更新日期: 2020-10-18阅读: 2.1k标签: 运算

前言

JavaScript 中的最大安全整数是 2 ^{53} – 1,即 9007199254740991,当我们进行超出这个范围的数值计算的时候就无法得到精确的值,而是一个近似值,比如我们计算 9007199254740991 + 10 得到的结果是 9007199254741000。本文讲一下如何利用字符串在 JavaScript 中实现大数相加相乘。


相加

用字符串实现相加相乘基本思路就是按照我们在纸上进行竖式运算一样。对于加法,我们需要将两个数 num1 和 num2 上下对齐,然后从个位开始计算两个数对应位的和,循环到最高位,将每一次运算的结果保存到一个数组 result 中去,最终用 Array.prototype.join() 方法还原成一个数组。

这里为了保持循环的正常进行,我们需要保证两个字符串位数相等,所以我们要用 String.prototpye.padStart() 方法将位数比较小的那一个字符串的前面用 '0' 补齐。

按位相加有个问题就是进位如何保存,我的思路是这样的。当我们相加 num1[i] 和 num2[i] 的时候,得到的最多是一个两位数,它将影响 result 的两位,即当前的 result[0] 位置和即将 unshift 到 result 中的一位。当前的 result[0] 位置的数就是计算 [i -1] 是得到的数的高位(即进位),我们将我们计算的值加上进位,得到的数在分成两位分别放到 result 中。

所以总结一下就是我们计算 num1[i] + num2[i] 得到一个两位数,这个两位数要先和 num1[i-1] + num2[i-1] 的结果的进位(即 result[0] 相加,然后在分成 high 和 low 两位,将 result[0] 的值用 low 位替换,然后将 high 位 unshift 到 result 最前面。可以参考下图理解。


所以我们每次计算都是确定一位和下一位的进位。最后代码如下:

let add = function (num1, num2) {
    if (isNaN(num1) || isNaN(num2)) return '';
    if (num1 === '0' || num2 === '0') return (num1 === '0' ? num2 : num1);

    let len = Math.max(num1.length, num2.length);
    num1 = num1.padStart(len, '0');
    num2 = num2.padStart(len, '0');

    let result = [];

    for (let i = len - 1; i >= 0; i--) {
        let sum = Number(num1[i]) + Number(num2[i]) + (result[0] || 0);
        let low = sum % 10;
        let high = Math.floor(sum / 10);

        result[0] = low;
        result.unshift(high);
    }
    return result.join('');
}

console.log(add('10', '9007199254740991')) //09007199254741001

代码中我们加了两个判断,判断两个参数是否是合法数字格式,以及如果一个数是 '0' 则直接返回另一个数。


相乘

相乘的逻辑要比相加复杂一点,但是总体思路还是根据竖式来实现算法,我画了一张图,我们借助图来说明。


相乘是一个两层循环,我们要循环一个数的位,每一位再与另一个数循环的每一位相乘。我们每次相乘的结果最多是一个两位数。但是与相加不同的是,相加的 high 每次都是 unshift 进去即可,而相乘的高位也要与 result 的位进行运算。

我们来看一看相乘的规律,当我们用 num1[i] * num2[j] 的时候,可能得到两位数,也可能得到一位数,我们都统一算作两位数,高位没有的就用 0 补齐,那么最后我们得到的结果将是一个 i + j 位的数(开头可能存在补齐的 0)。而我们每次计算 num1[i] * num2[j] 的结果影响到的都是 result 中的 i + j 和 i + j + 1 位。

和加法中逻辑一样,我们将 num1[i] * num2[j] 的结果和 result[i + j + 1] 相加,得到的结果分为 low 和 high 分别存入 reslut 的 [i + j +1] 和 [i +j] 中。但是这里要注意,和加法不同,加法的高位直接存入就可以,我们这里的 high 对应的 result[i + j] 可能已经有值了,我们需要将已经存在的值加上。

high 和 result[i +j] 的相加可能存在进位怎么办呢,看上图中右边的当前 result 值中我们可以看到有些位存了不止一位数,我们将 high + result[i +j] 的值直接连进位一起保存到 result[i + j] 中。为什么能这样做呢,因为下次计算 num1[i] * num2[j - 1] 的时候(注意我们是从后往前遍历),会把 result[i + j]和 low 相加,进位自然能被处理,这也是这个算法比较重要的地方。

最后的代码:

let multiply = function (num1, num2) {
    if (isNaN(num1) || isNaN(num2)) return '';
    if (num1 === '0' || num2 === '0') return '0';

    let l1 = num1.length,
        l2 = num2.length;

    let result = [];

    for (let i = l1 -1; i >= 0; i--) {
        for (let j = l2 - 1; j >= 0; j--) {
            let index1 = i + j;
            let index2 = i + j + 1;

            let product = num1[i] * num2[j] + (result[index2] || 0);
            result[index2] = product % 10;
            result[index1] = Math.floor(product / 10) + (result[index1] || 0);
        }
    }
    return result.join('').replace(/^0+/, '');
}

console.log(multiply('123', '234')) //28782

代码中加了两个判断:是否是合法数字,如果有一个值为 0 则直接返回 0。注意最后要判断得到的结果是否开头有 0,如果有则要去掉,这里用的正则表达式。

转载文章请注明:JavaScript 大数相加相乘实现 - https://www.clloz.com/programming/front-end/js/2020/10/18/javascript-bignumber-add-multiply/ 

 

链接: https://www.fly63.com/article/detial/9740

js除了Math.floor方法,还可以通过位运算|,>>实现向下取整

我们都知道通过Math.floor()方法可实现数值的向下取整,得到小于或等于该数字的最大整数。除了Math.floor方法,还可以使用位运算|,>>来实现向下取整哦

es6 扩展运算符 三个点(...)

扩展运算符( spread )是三个点(...)。它好比 rest 参数的逆运算,将一个数组转为用逗号分隔的参数序列。

巧用JS位运算

位运算的方法在其它语言也是一样的,不局限于JS,所以本文提到的位运算也适用于其它语言。位运算是低级的运算操作,所以速度往往也是最快的

js中使用位运算,让执行效率更高

平常的数值运算,其本质都是先转换成二进制再进行运算的,而位运算是直接进行二进制运算,所以原则上位运算的执行效率是比较高的,由于位运算的博大精深,下面通过一些在js中使用位运算的实例

js各种取整方式及方法_四舍五入、向上取整、向下取整

js实现:四舍五入、向上取整、向下取整等方法。parseInt、Math.ceil、Math.round、Math.floor、toFixed等的使用

JavaScript循环计数器

JS经常会遇到延迟执行的动作,并且失败后自动尝试,尝试N次之后就不再尝试的需求,今天刚好又遇到,于是写个闭包,以后不断完善继续复用。检查并计数第一个参数用来标记是尝试哪个动作的,第二个参数是最大尝试次数

js 位运算符_js按位运算符及其妙用

大多数语言都提供了按位运算符,恰当的使用按位运算符有时候会取得的很好的效果。在我看来按位运算符应该有7个:& 按位与、| 按位或、^ 按位异或、~ 按位非

PHP取整、四舍五入取整、向上取整、向下取整、小数截取

PHP取整数函数常用的四种方法:1.直接取整,舍弃小数,保留整数:intval(); 2.四舍五入取整:round(); 3.向上取整,有小数就加1:ceil(); 4.向下取整:floor()。

JavaScript 中的相等操作符 ( 详解 [] == []、[] == ![]、{} == !{} )

ECMAScript 中的相等操作符由两个等于号 ( == ) 表示,如果两个操作数相等,则返回 true。相等操作符会先转换操作数(通常称为强制转型),然后比较它们的相等性。

关于js开发中保留小数位计算函数(以向上取整或向下取整的方式保留小数)

前端工作中经常遇到数字计算保留小数问题,由于不是四舍五入的方式不能使用toFixed函数,本文采用正则表达式匹配字符串的方式,解决对数字的向上或向下保留小数问题:

点击更多...

内容以共享、参考、研究为目的,不存在任何商业目的。其版权属原作者所有,如有侵权或违规,请与小编联系!情况属实本人将予以删除!