你的位置:首页 > 软件开发 > Java > Code Kata:大整数比较大小大整数四则运算

Code Kata:大整数比较大小大整数四则运算

发布时间:2017-12-08 06:00:06
大整数的四则运算已经是老生常谈的问题了。很多的库也已经包含了各种各样的解决方案。作为练习,我们从最简单的加减法开始。加减法的核心思路是用倒序数组来模拟一个大数,然后将两个大数的利用竖式进行运算。加法函数:异符号相加时调用减法函数(减法函数后面给出)同符号相加先确定符号因为输入输出 ...

Code Kata:大整数比较大小大整数四则运算

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

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

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

加法函数

  • 异符号相加时调用减法函数(减法函数后面给出)
  • 同符号相加先确定符号
  • 因为输入输出的为字符串,需要去除字符串开头的0
 1 function add(a, b) { /*输入两个字符串类型大数字*/ 2  3  if(a.indexOf('-') >= 0 && b.indexOf('-') < 0){ 4  5   return minus(b,a); 6  } 7  else if(a.indexOf('-') < 0 && b.indexOf('-') >= 0){ 8  9   return minus(a,b);10  }11 12  var sign = "";13 14  if(a.indexOf('-') >= 0 && b.indexOf('-') >= 0){ /*两个负数相加,指定符号*/15 16   sign = "-";17 18   a = a.substr(1);19 20   b = b.substr(1);21  }22 23  var aArr = a.replace(/^0+/,'').split('').reverse();24 25  var bArr = b.replace(/^0+/,'').split('').reverse(); /*利用倒序数组存储*/26 27  var carry = 0; /*进位值*/28 29  var sumArr = [];30 31  var len = Math.max(aArr.length, bArr.length); /*取得位数较大的一个数的位数*/32 33  for(var i=0;i<=len-1;i++){34 35   var digA = parseInt(aArr[i]) ? parseInt(aArr[i]) : 0;36 37   var digB = parseInt(bArr[i]) ? parseInt(bArr[i]) : 0;38 39   var digTotal = digA + digB + carry;40 41   if(i == len-1){/*排除'012' + '012'这样的情况*/42 43    if(digTotal > 0){44 45     sumArr.unshift(digTotal);46    }47 48    break;49   }50 51   carry = Number(digTotal >= 10);52 53   digTotal = digTotal % 10;54 55   sumArr.unshift(digTotal);56 57  }58 59  return sign + sumArr.join('');60 }

 

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

比较小大函数:

  • 异符号比较大小,正数大于负数
  • 正数比较大小,先比较长度,长度大的数值大
  • 正数长度一致,从最高位开始逐位比较,只到出现较大的一方,则数值更大
  • 负数比较大小,方法同正数,结果取反即可
  • 因为输入输出的为字符串,需要去除字符串开头的0
 1 function compare(a,b){ 2  3  var sign = 1; 4  5  if(a.indexOf('-') >= 0 && b.indexOf('-') < 0){ /*异符号比较*/ 6  7   return -1; 8  } 9  else if(a.indexOf('-') < 0 && b.indexOf('-') >= 0){ /*异符号比较*/10 11   return 1;12  }13  else if(a.indexOf('-') >= 0 && b.indexOf('-') >= 0){ /*同为负数,指定取反,同时改为正数比较方式*/14 15   sign = -1;16 17   a = a.substr(1);18 19   b = b.substr(1);20  }21 22  a = a.replace(/^0+/,'');23 24  b = b.replace(/^0+/,'');25 26  var flag;27 28  if(a.length < b.length){ /*比较长度*/29 30   flag = -1;31  }32  else if(a.length > b.length){33 34   flag = 1;35  }36  else{37 38   flag = 0;39  }40 41  if(flag == 0){ /*相同长度逐位比较*/42 43   var aArr = a.split('');44 45   var bArr = b.split('');46 47   for(var i=0;i<=aArr.length;i++){48 49    if(aArr[i] > bArr[i]){50 51     flag = 1;52 53     break;54    }55    else if(aArr[i] > bArr[i]){56 57     flag = -1;58 59     break;60    }61   }62  }63 64  return sign * flag;65 }

 

减法函数:

  • 异符号相减时调用加法函数
  • 同符号相减需要先确定大小
  • 因为输入输出的为字符串,需要去除字符串开头的0
 1 function minus(a, b) { 2  3  if(a.indexOf('-') >= 0 && b.indexOf('-') < 0){ 4  5   return add(a,"-" + b); 6  } 7  else if(a.indexOf('-') < 0 && b.indexOf('-') >= 0){ 8  9   a = a.substr(1);10 11   return add(a,b);12  }13 14  var sign = "";15 16  if(compare(a,b) < 0){17 18   var temp = b;19 20   b = a;21 22   a = temp;23 24   sign = "-";25  }26 27  var aArr = a.replace(/^0+/,'').split('').reverse();28 29  var bArr = b.replace(/^0+/,'').split('').reverse(); /*利用倒序数组存储*/30 31  var borrow = 0; /*借位值*/32 33  var minusArr = [];34 35  var len = Math.max(aArr.length, bArr.length); /*取得位数较大的一个数的位数*/36 37  for(var i=0;i<=len-1;i++){38 39   var digA = parseInt(aArr[i]) ? parseInt(aArr[i]) : 0;40 41   var digB = parseInt(bArr[i]) ? parseInt(bArr[i]) : 0;42 43   var digMinus;44 45   if(i == len-1){46 47    if(digA - borrow <= digB){ /*最高位不够减直接跳出循环*/48 49     break;50    }51   }52 53   if(digA - digB - borrow >= 0){54 55    digMinus = digA - digB - borrow;56 57   }else{58 59    digMinus = digA + 10 - digB - borrow;60 61    borrow = 1;62   }63 64   minusArr.unshift(digMinus);65 66  }67 68  return sign + minusArr.join('');69 }

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

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

 


 

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

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

原标题:Code Kata:大整数比较大小大整数四则运算

关键词:

*特别声明:以上内容来自于网络收集,著作权属原作者所有,如有侵权,请联系我们: admin#shaoqun.com (#换成@)。

可能感兴趣文章

我的浏览记录