如何实现大整数相加？-菜鸟笔记

我们平时实现两个整数相加，直接用两个int类型的整数相加即可。如果整数再大一点，那么就可以将整数声明为long类型。如果整数是数十位的，甚至是上百位的，连long类型也装不下呢？让我们来先回顾一下我们上小学时是如何计算两个较大的整数想加的。小学时，要计算两个较大整数相加，就要进行列竖式计算，将两个整数先右对齐，再从个位开始，到十位，到百位......依次进行加法运算。那么我们为什么要列出竖式运算呢？因为我们人脑无法将两个很大的数一步到位直接计算出结果，必须拆解成一位一位的运算。同样，程序不可能通过一条指令就计算出两个大整数的和，也必须一位一位的运算。但是大整数既然超过了long类型的范围，那么计算机如何来存储大整数呢？于是数组就派上用场了。我们可以用数组来存储大整数的每一位。

我以426709752318 + 95481253129为例，来看看计算机进行两个大整数相加的具体操作步骤：

第一步：由于我们都习惯从左往右地访问数组，因此把整数倒序存储，整数的个位存于数组0下标位置，最高位存于数组长度减1下标位置处。

第二步：创建结果数组，该数组的长度应为较大整数的位数加1。

第三步：遍历两个整数的数组，左对齐从左到右按照对应下标将元素相加。

例子中，首先相加的是数组A的第一个元素8和数组B的第一个元素9，得出结果7，进位1。把7填充到Result数组的对应下标，进位的1填充至下一位置：

第二组相加的是数组A的第二个元素1和数组B的第二个元素2，得出结果3，再加上刚才的进位1，结果是4，将4填充至Result数组的对应下标处：

第三组相加的是数组A的第三个元素3和数组B的第三个元素1，得出结果4，将4填充至Result数组的对应下标处：

第四组相加的是数组A的第四个元素2和数组B的第四个元素3，得出结果5，将5填充至Result数组的对应下标处：

以此类推......一直把两个数组的所有元素都相加完毕：

第四步:把Result数组的全部元素再次逆序，去掉首位，即可得到最终结果：

代码如下：

/**
 * 大整数求和
 * @param bigNumberA 大整数A
 * @param bigNumberB 大整数B
 */

 public static String bigNumberSum(String bigNumberA, String bigNumberB) {
     // 1.把两个大整数用数组逆序存储，数组长度等于较大整数位数+1
     int maxLength = bigNumberA.length() > bigNumberB.length() ? bigNumberA.length() : bigNumberB.length();
     int[] arrayA = new int[maxLength + 1];
     int[] arrayB = new int[maxLength + 1];
     for(int i = 0; i < bigNumberA.length(); i++)
         arrayA[i] = bigNumberA.charAt(bigNumberA.length() - 1 - i) - '0';
    
     for(int i = 0; i < bigNumberB.length(); i++)
         arrayB[i] = bigNumberB.charAt(bigNumberB.length() - 1 - i) - '0';

    // 2.构建result数组，数组长度等于较大整数位数 + 1
    int[] result = new int[maxLength + 1];
    // 3.遍历数组，按位相加
    for(int i = 0; i < result.length; i++) {
        int temp = result[i];
        temp += arrayA[i] + arrayB[i];
        // 判断是否进位
        if(temp >= 10) {
            temp = temp - 10;
            result[i + 1] = 1;
        }
        result[i] = temp;
    }

    // 4.把result数组再次逆序并转成String
    StringBuilder sb = new StringBuilder();
    //是否找到大整数的最高有效位
    boolean findFirst = false;
    for(int i = result.length - 1; i >= 0; i--) {
        if(!findFirst) {
            if(result[i] == 0)
                continue;

            findFirst = true;
        }
        sb.append(result[i]);
    }
    
    return sb.toString();
 } 
 

 public static void main(String[] args) {
     System.out.println(bigNumberSum("426709752318", "95481253129"));
 }

我们来分析下这个算法的时间复杂度，如果给定的大整数的最长位数是n，那么创建数组、按位计算、结果逆序的时间复杂度均是O(n),因此整体时间复杂度是O(n)。

这个还有一个优化的地方。我们之前是把大整数按照每一个十进制数位来拆分，比如较大整数位的长度有50位，那么我们需要创建一个51位的数组，数组的每个元素均存储一位。

我们真的有必要把整数拆得那么细吗？很显然没必要。只需要拆分到可以被直接计算的程度即可。

我们都知道int类型的取值范围是-2147483648~2147483647，最多有10位整数。为了防止溢出，我们可以把大整数的每9位作为数组的一个元素进行加法运算。

如此一来，占用空间和运算次数都被压缩了9倍。其实，在Java中，工具类BigInteger和BigDecimal的底层实现也是把大整数拆分成数组进行运算，与此方法大体相同。

面试题

如何实现大整数相加？

笔记导航