大整数求和

大整数是指超出了计算机的表示范围的数,这类数的基本运算无法使用加减乘除直接运算,通常可以使用数组存储大整数,使用字符串来表示这样的整数。

什么是大整数

大整数是指超出了计算机的表示范围的数,这类数的基本运算无法使用加减乘除直接运算,通常可以使用数组存储大整数,使用字符串来表示这样的整数。数组的每一个元素对应整数的每一位。

既然已经按位存储了大整数,加法计算就可以使用原始的竖式进行,每一位分别计算,有进位则加到下一位。

大整数求和

给定两个大整数,计算它们的和,根据竖式的计算规则进行按位运行;使用数组存储整数;

下面是大整数求和的算法步骤:

  1. 将给定的大整数倒序存放到数组中,原因是竖式是从右开始计算,而习惯上访问数组从左边开始。
  2. 创建存放结果的数组,长度位较大整数的位数+1
  3. 遍历两个数组,从左到右将两个数组对应位置的数和结果数组中对应的进位数相加
    a) 如果相加结果<10,则存储到结果数组
    b) 如果相加结果>10,则将结果除以10,余数存放到结果数组,商存放到结果数组的下一位代表进位。
  4. 最后将结果数组逆序得到最终的结果

具体的Java代码如下:

public static String largeIntegerSumImp(String numA,String numB){
    int lengthA=numA.length();
    int lengthB=numB.length();
    int maxLength=lengthA>lengthB?lengthA:lengthB+1;
    int[] arrayA=new int[maxLength+1];
    int[] arrayB=new int[maxLength+1];
    int[] result=new int[maxLength+1];
    int i=0; //将字符串逆序存储到数组中
    for(i=0;i<lengthA;i++) {
        arrayA[i]=numA.charAt(lengthA-i-1)-'0';
    }
    for(i=0;i<lengthB;i++) {
        arrayB[i]=numB.charAt(lengthB-i-1)-'0';
    }
    //进行大整数求和
    for(i=0;i<result.length;i++) {
        int add=result[i]+arrayA[i]+arrayB[i];  //位数和进位相加
        if(add<10) {  //没有进位
            result[i]=add;
            continue;
        }
        int remainder=add%10;  //余数
        int quotient=add/10;  //商
        result[i]=remainder;  
        if(i!=result.length-1) {   
            result[i+1]=quotient;
        }
    }
    //再将数组逆序得到最终的结果
    String sum="";
    int lastIndex=0;
    for(i=maxLength-1;i>=0;i--) {  //去除数组最后的0
        if(result[i]!=0) {
            lastIndex=i;
            break;
        }
    } 
    for(i=lastIndex;i>=0;i--) {
        sum+=result[i];
    }
    return sum;
}

大整数求和的基本步骤如下图所示:
大整数求求和图片展示

总结

在以上的算法中,有几个小细节需要注意:

  • 计算时使用结果数组进行遍历,注意进位,最后一次循环不做进位
  • 逆序结果时,首先要去除掉最后的0,因为result数组中默认初始化位0

优化

大整数求和也有可以优化的情形,当位数足够大时,按位存储整数也会花费巨大的空间并且增大了运算次数;

为了优运算,可以一次在数字元素中存储多位,只要计算机能够表示这个多位的数即可;

比如加上有一个30位的数,按照原始方法,需要31长度的数组;如果按照9位拆分,每一存储一个9位数,这样只需要数组的长度位4,因为一个元素可以表示9位数的大小(int最多有10位数),当然也可以选择使用long类型的数组,这样可以拆分为长度更小的数组,存储空间和运算次数都大大降低。

smartpig wechat
扫一扫关注微信公众号
0%