谈谈JS中的大数运算

发表于 | 阅读次数

什么是大数运算

大数运算顾名思义就是一些很大的数之间的运算。之所以要用大数运算算法处理原因有二：

  1. 我们知道计算机能表现的数字范围是有限的，超过这个范围会出现溢出。
  2. 在js中只有一定范围内的数才能精确到个位，超过这个范围的数是不准确的。有关js中的数字可以参考下图：
    image

算法

在这里我以加法为例，介绍三个大数运算的方法。

方法一：常规方法

思路就是运用加法的原理，一位一位的加

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
function add(a,b) {
    // 初始化，把两个数字转为数组
    // 这里将数组反过来是因为两个数字长短不一，反过来有助于处理边界问题
    if (a.length>=b.length) {
		var lgArr = a.split("").reverse(), smArr = b.split("").reverse();
	}else{
		var lgArr = b.split("").reverse(), smArr = a.split("").reverse();
	}
    var lgLength = lgArr.length,
		res = '';	
	for(var i=0; i<lgLength; i++){
		lgArr[i] = +lgArr[i] + +smArr[i];// 使用一元加来将字符串转成数字
		if(lgArr[i]>10){// 如果大于10代表要进位
			lgArr[i] -= 10;
			if(i==lgLength-1){
				lgArr[i+1] = 1;
			}else{
				lgArr[i+1] = +lgArr[i+1] + 1;
			}
		}
	}
	res = lgArr.reverse().join("");
	return res;
}

方法二：利用js的奇淫技巧

JS中有很多奇淫技巧，合理运用可以让代码看起来更简洁

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
function add1(a,b){
	// ~取反操作符，~0 === -1，~~0 === 0，~~null === 0，~~'0' === 0
	// 用+也能实现字符转成数字，不过~~能处理null的情况
	// c>0会返回一个布尔值，布尔值转换成数字的时候true为1，false为0
	var res = '',
		c = 0;
	a = a.split('');
	b = b.split('');
	while(a.length||b.length||c){
		c = c + ~~a.pop() + ~~b.pop();
		res = c % 10 + res;
		c = c > 9;
	}
	return res.replace(/^0+/,'');// 去掉前面可能存在的0
}

方法三：快速算法

前两种一位一位的加太慢了，我们可以充分利用js的精度，14位14位的算。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
function add2(a,b){
	// 主要思想是分开一段段加，这样既能保证精度且不溢出，也能提高速度
	// 使用到了substr这个方法，String.substr(idx,length)接收两个参数，第一个参数是索引，第二个参数是长度，第二个参数可省略
	// 如果索引超范围，或者长度小于1那么返回空字符串
	var res = [];
	while(a.length||b.length){
		res.push(parseInt(a.substr(-14)||0,10)+parseInt(b.substr(-14)||0,10));
		a = a.substr(0,a.length-14);
		b = b.substr(0,b.length-14);
	}
	var c = 0, o = '';
	console.log(res)
	while(res.length){
		let temp = (res.shift() + c).toString();
		o = temp.substr(-14) + o;
		c = parseInt(temp.substr(0,temp.length-14) || 0,10);
	}
	return o;
}

实际上只用一个循环就可以了，上面只是方便理解。只用一个循环的话就是这样：

1
2
3
4
5
6
7
8
9
10
11
function add3(a,b){
	var res = '', c = 0;
	while(a.length||b.length){
		let temp = (parseInt(a.substr(-14)||0,10)+parseInt(b.substr(-14)||0,10) + c).toString();
		res = temp.substr(-14) + res;
		c = parseInt(temp.substr(0,temp.length-14,10)||0,10);
		a = a.substr(0,a.length-14);
		b = b.substr(0,b.length-14);
	}
	return res;
}