Preface

Q: there are two big integers, which cannot be stored as large as long. How to add them?
A: . . .

thinking

To solve this problem, there are two problems to be solved:

• How to store two large integers
• Summation

If long cannot be stored, then this number must be very large, and can only be stored in other ways. We can use strings to store data. Strings are unlimited in length, and any large number can be saved. But another problem is that strings cannot be added

Recall to add integers. If we manually operate on paper, first align the numbers from single digits, and then add them one by one. If the result is greater than 10, carry them, as shown below:

If the string elements are stored in the array, the array is traversed, and the bits are added from the beginning. Pay attention to carry, and the result is still saved in an array. Simulate the manual calculation method, and finally the correct result will be obtained.

Realization

public static int[] bigNumAdd(String s1, String s2){
    //Creating an int array from a string
    int[] n1 = createIntArray(s1);
    int[] n2 = createIntArray(s2);
    //The length of the result array should be the longest array length plus 1, because when two numbers are added, the result will increase 1 digit at most, and it is impossible to increase two or more digits
    int rLength = n1.length > n2.length ? n1.length + 1 : n2.length + 1;
    int[] result = new int[rLength];
    
    //Reverse the two arrays so that the number of bits in front of the array is convenient for calculation and alignment
    reverseArray(n1);
    reverseArray(n2);
    int temp = 0;
    int bTemp = 0;
    int num1 = 0;
    int num2 = 0;
    //The number of iterations is result.length - 1, which is the length of the longest additive array
    for (int i = 0; i < result.length - 1; i++) {
        //Ensure that the two addends are not out of bounds
        if (i < n1.length) {
            num1 = n1[i];
        }else {
            num1 = 0;
        }
        
        if (i < n2.length) {
            num2 = n2[i];
        }else {
            num2 = 0;
        }
        //Add two numbers in the same position, and pay attention to add the result element in the original position, because carry may be generated in the previous calculation
        temp = num1 + num2 + result[i];
        //Carry is calculated. If the sum result is greater than 10, there must be carry. Because it is the sum of two numbers, the carry value can only be 1
        if (temp >= 10) {
            bTemp = 1;
            temp = temp - 10;
        }else {
            bTemp = 0;
        }
        //Set the result value of the current bit and the carry value of the next bit
        result[i] = temp;
        if (bTemp > 0) {
            result[i+1] = bTemp;
        }
    }
    //Remove the high redundant 0 in the result
    result = removeZero(result);
    //Then, the results are inverted to get the expected results
    reverseArray(result);
    System.out.println(" bigNumAdd " + Arrays.toString(result));
    return result;
}

The specific implementation is as above. There are corresponding instructions in the addition place. It should be easier to understand. See my github for specific code