两个大位数相乘问题

模拟乘法累加

• 第一步，是将乘数与被乘数逐位相乘；
• 第二步，将逐位相乘得到的结果，对应相加起来，这一步不考虑进位。
• 第三步，从后面开始循环遍历，n/10 表示进位数，n%10 表示当前位的值

        9  8
×       2  1
-------------
       (9)(8)  <---- 第1趟: 98×1的每一位结果 
  (18)(16)     <---- 第2趟: 98×2的每一位结果 
-------------
  (18)(25)(8)  <---- 这里就是相对位的和，还没有累加进位 

代码实现：

/**
     * 两个大数相乘算法
     *
     * @param numberStr1
     * @param numberStr2
     * @return
     */
    public static String bigIntMultiply(String numberStr1, String numberStr2) {
        int[] numberInt1 = charArray2IntArray(numberStr1.toCharArray());
        int[] numberInt2 = charArray2IntArray(numberStr2.toCharArray());

        int[] result = new int[numberInt1.length + numberInt2.length];

        for (int j = numberInt2.length - 1; j >= 0; j--) {
            int[] array = new int[numberInt1.length + numberInt2.length - 1 - j];  //numberInt2.length - 1 - j 表示后面需要补0 的位数
            int i = numberInt1.length - 1;
            for (; i >= 0; i--) {
                array[i] = numberInt2[j] * numberInt1[i];
            }
            result = arrayAdd(result, array);  //两个数组相加
        }

        //处理进位问题
        for (int k = result.length - 1; k >= 0; k--) {
            int n = result[k] / 10;
            int m = result[k] % 10;
            result[k] = m;
            if (n != 0) {
                result[k - 1] = n + result[k - 1];
            }
        }

        return Arrays.toString(result).replace(", ", "").replace("[", "").replace("]", "").replaceFirst("^(0+)", "");
    }

    /**
     * 两个数组相加
     *
     * @param array1
     * @param array2
     * @return
     */
    private static int[] arrayAdd(int[] array1, int[] array2) {
        int k = 1;
        int[] result = new int[array1.length > array2.length ? array1.length + 1 : array2.length + 1];
        while (true) {
            int n = 0;
            if (array1.length - k >= 0) {
                n = array1[array1.length - k];
            }
            int m = 0;
            if (array2.length - k >= 0) {
                m = array2[array2.length - k];
            }
            if (n == 0 && m == 0) {
                break;
            }
            result[result.length - k++] = m + n;
        }
        return result;
    }


    private static int[] charArray2IntArray(char[] array) {
        int length = array.length;
        int[] result = new int[length];
        for (int i = 0; i < length; i++) {
            result[i] = array[i] - '0';
        }
        return result;
    }