大整数运算

2018-09-27 22:42:13

一、大整数加法

问题描述：

问题求解：

    public String addStrings2(String num1, String num2) {
        if (num1.length() < num2.length()) return addStrings(num2, num1);
        char[] n1 = num1.toCharArray(), n2 = num2.toCharArray();
        int m = n1.length, n = n2.length;
        int carry = 0, i = 1, sum = 0;
        while (i <= n) {
            sum = n1[m - i] + n2[n - i] - '0' * 2 + carry;
            carry = sum / 10;
            n1[m - i] = (char) (sum % 10 + '0');
            i++;
        }
        while (carry > 0 && i <= m) {
            sum = n1[m - i] + carry - '0';
            carry = sum / 10;
            n1[m - i] = (char) (sum % 10 + '0');
            i++;
        }
        return carry == 0 ? new String(n1) : "1" + new String(n1);
    }

二、大整数乘法

问题描述：

问题求解：

`num1[i] * num2[j]` will be placed at indices `[i + j`, `i + j + 1]` 

    public String multiply(String num1, String num2) {
        int len1 = num1.length();
        int len2 = num2.length();
        int[] res = new int[len1 + len2];
        for (int i = len1 - 1; i >= 0; i--) {
            for (int j = len2 - 1; j >= 0; j--) {
                int mul = (num1.charAt(i) - '0') * (num2.charAt(j) - '0');
                int p1 = i + j;
                int p2 = i + j + 1;
                int sum = mul + res[p2];
                res[p1] += sum / 10;
                res[p2] = sum % 10;
            }
        }
        StringBuffer sb = new StringBuffer();
        for (int i = 0; i < res.length; i++) if (!(sb.length() == 0 && res[i] == 0)) sb.append(res[i]);
        return sb.length() == 0 ? "0" : sb.toString();
    }