Code Kata:大整数比较大小&大整数四则运算---加减法 javascript实现

大整数的四则运算已经是老生常谈的问题了。很多的库也已经包含了各种各样的解决方案。

作为练习,我们从最简单的加减法开始。

加减法的核心思路是用倒序数组来模拟一个大数,然后将两个大数的利用竖式进行运算。

加法函数:

  • 异符号相加时调用减法函数(减法函数后面给出)
  • 同符号相加先确定符号
  • 因为输入输出的为字符串,需要去除字符串开头的0
 function add(a, b) { /*输入两个字符串类型大数字*/

     if(a.indexOf('-') >= 0 && b.indexOf('-') < 0){

         return minus(b,a);
}
else if(a.indexOf('-') < 0 && b.indexOf('-') >= 0){ return minus(a,b);
} var sign = ""; if(a.indexOf('-') >= 0 && b.indexOf('-') >= 0){ /*两个负数相加,指定符号*/ sign = "-"; a = a.substr(1); b = b.substr(1);
} var aArr = a.replace(/^0+/,'').split('').reverse(); var bArr = b.replace(/^0+/,'').split('').reverse(); /*利用倒序数组存储*/ var carry = 0; /*进位值*/ var sumArr = []; var len = Math.max(aArr.length, bArr.length); /*取得位数较大的一个数的位数*/ for(var i=0;i<=len-1;i++){ var digA = parseInt(aArr[i]) ? parseInt(aArr[i]) : 0; var digB = parseInt(bArr[i]) ? parseInt(bArr[i]) : 0; var digTotal = digA + digB + carry; if(i == len-1){/*排除'012' + '012'这样的情况*/ if(digTotal > 0){ sumArr.unshift(digTotal);
} break;
} carry = Number(digTotal >= 10); digTotal = digTotal % 10; sumArr.unshift(digTotal); } return sign + sumArr.join('');
}

在写减法时,发现需要先比较大小,因此需要一个大数字比较大小的函数

比较小大函数:

  • 异符号比较大小,正数大于负数
  • 正数比较大小,先比较长度,长度大的数值大
  • 正数长度一致,从最高位开始逐位比较,只到出现较大的一方,则数值更大
  • 负数比较大小,方法同正数,结果取反即可
  • 因为输入输出的为字符串,需要去除字符串开头的0
 function compare(a,b){

     var sign = 1;

     if(a.indexOf('-') >= 0 && b.indexOf('-') < 0){ /*异符号比较*/

         return -1;
}
else if(a.indexOf('-') < 0 && b.indexOf('-') >= 0){ /*异符号比较*/ return 1;
}
else if(a.indexOf('-') >= 0 && b.indexOf('-') >= 0){ /*同为负数,指定取反,同时改为正数比较方式*/ sign = -1; a = a.substr(1); b = b.substr(1);
} a = a.replace(/^0+/,''); b = b.replace(/^0+/,''); var flag; if(a.length < b.length){ /*比较长度*/ flag = -1;
}
else if(a.length > b.length){ flag = 1;
}
else{ flag = 0;
} if(flag == 0){ /*相同长度逐位比较*/ var aArr = a.split(''); var bArr = b.split(''); for(var i=0;i<=aArr.length;i++){ if(aArr[i] > bArr[i]){ flag = 1; break;
}
else if(aArr[i] > bArr[i]){ flag = -1; break;
}
}
} return sign * flag;
}

减法函数:

  • 异符号相减时调用加法函数
  • 同符号相减需要先确定大小
  • 因为输入输出的为字符串,需要去除字符串开头的0
 function minus(a, b) {

     if(a.indexOf('-') >= 0 && b.indexOf('-') < 0){

         return add(a,"-" + b);
}
else if(a.indexOf('-') < 0 && b.indexOf('-') >= 0){ a = a.substr(1); return add(a,b);
} var sign = ""; if(compare(a,b) < 0){ var temp = b; b = a; a = temp; sign = "-";
} var aArr = a.replace(/^0+/,'').split('').reverse(); var bArr = b.replace(/^0+/,'').split('').reverse(); /*利用倒序数组存储*/ var borrow = 0; /*借位值*/ var minusArr = []; var len = Math.max(aArr.length, bArr.length); /*取得位数较大的一个数的位数*/ for(var i=0;i<=len-1;i++){ var digA = parseInt(aArr[i]) ? parseInt(aArr[i]) : 0; var digB = parseInt(bArr[i]) ? parseInt(bArr[i]) : 0; var digMinus; if(i == len-1){ if(digA - borrow <= digB){ /*最高位不够减直接跳出循环*/ break;
}
} if(digA - digB - borrow >= 0){ digMinus = digA - digB - borrow; }else{ digMinus = digA + 10 - digB - borrow; borrow = 1;
} minusArr.unshift(digMinus); } return sign + minusArr.join('');
}

以上给出的是带符号大整数加减法基础实现,但效率并不是特别高。

网上也有通过10000进制优化的竖式算法,以及通过位运算实现四则运算的方法,大家也可以搜索看看,今天的练习就到这里了,下周会给出乘除法的基本实现。


如果喜欢我的文章,可以扫描二维码关注我的微信公众号

争取每天都分享一点我自己的开发和练习体验~
Code Kata:大整数比较大小&大整数四则运算---加减法 javascript实现

上一篇:Java的Integer常量池和String常量池


下一篇:vc++ 中 IntelliSense: 无法打开 源 文件 "xxx.h"