Big Number Operation

Algorithm

This is the conclusion for big number(the number cannot be presented by Integer) operations. Doesn't contains negetive or float number cases.

1. 加法运算:

private static String addOperation(String num1, String num2) {
        StringBuilder result = new StringBuilder();
        int carry = 0;
        int len1 = num1.length() - 1;
        int len2 = num2.length() - 1;
        while (len1 >= 0 || len2 >= 0 || carry > 0) {
            int localRes;
            if (len1 >= 0 && len2 >= 0)
                localRes = Character.getNumericValue(num1.charAt(len1))
                        + Character.getNumericValue(num2.charAt(len2)) + carry;
            else if (len1 >= 0)
                localRes = Character.getNumericValue(num1.charAt(len1)) + carry;
            else
                localRes = carry;
            carry = localRes / 10;
            localRes = localRes % 10;
            result.insert(0, String.valueOf(localRes));
            len1--;
            len2--;
        }
        return result.toString();
    }

2. 减法运算:

保持被减数大于减数，需要checkBigger方法辅助比较，并做好符号标记。

private static String subsOperation(String num1, String num2) {
        String neg="";
        if (checkBigger(num1, num2) > 0) {
            String tmp = num1;
            num1 = num2;
            num2 = tmp;
            neg="-";
        }
        StringBuilder result = new StringBuilder();
        int carry = 0;
        int len1 = num1.length() - 1;
        int len2 = num2.length() - 1;
        while (len1 >= 0 || len2 >= 0 || carry > 0) {
            int localRes;
            if (len1 >= 0 && len2 >= 0)
                localRes = Character.getNumericValue(num1.charAt(len1))
                        - Character.getNumericValue(num2.charAt(len2)) - carry;
            else
                localRes = Character.getNumericValue(num1.charAt(len1)) - carry;
            if (localRes < 0) {
                localRes = localRes + 10;
                carry = 1;
            } else
                carry = 0;
            result.insert(0, String.valueOf(localRes));
            len1--;
            len2--;
        }
        String res = result.toString();
        while (res.charAt(0) == '0')
            res = res.substring(1);
        return neg+res;
    }
    private static int checkBigger(String num1, String num2) {
        int len1 = num1.length() - 1;
        int len2 = num2.length() - 1;
        if (len1 > len2)
            return -1;
        else if (len1 < len2)
            return 1;
        else {
            for (int i = 0; i < len1; i++) {
                if (Character.getNumericValue(num1.charAt(i)) == Character
                        .getNumericValue(num2.charAt(i)))
                    continue;
                else
                    return Character.getNumericValue(num1.charAt(i)) < Character
                            .getNumericValue(num2.charAt(i)) ? 1 : -1;
            }
        }
        return 0;
    }

3. 乘法运算：

模拟竖式运算，先用数组记录俩个digit的乘积，mark竖式里的递进位置，通过数组标记位置实现累加，得出整个数组后，最后再考虑进位问题。

private static String mulOperation(String num1, String num2) {
        int len1 = num1.length() - 1;
        int len2 = num2.length() - 1;
        int[] res = new int[len1 + len2 + 2];
        int mark = 0;
        for (int i = len1; i >= 0; i--) {
            for (int j = len2; j >= 0; j--) {
                res[len2 - j + mark] += Character.getNumericValue(num1
                        .charAt(i)) * Character.getNumericValue(num2.charAt(j));
            }
            mark++;
        }
        StringBuilder result = new StringBuilder();
        int carry = 0;
        for (int i = 0; i < res.length; i++) {
            int localRes = res[i] + carry;
            carry = localRes / 10;
            localRes = localRes % 10;
            result.insert(0, String.valueOf(localRes));
        }
        String product = result.toString();
        while (product.charAt(0) == '0')
            product = product.substring(1);
        return product;
    }

4. 除法运算并求模

同样是通过数组标记，但需要用减法来辅助，并且需要除数移位补零操作。

private static String divOperation(String num1, String num2) {
        int mark = 1;
        String newnum2 = new String(num2);
        while (checkBigger(num1, newnum2 + "0") < 0) {
            newnum2 += "0";
            mark++;
        }
        int[] res = new int[mark];
        while (checkBigger(num1, num2) <= 0) {
            num1 = subsOperation(num1, newnum2);
            res[mark - 1]++;
            while (checkBigger(num1, newnum2) > 0) {
                newnum2 = newnum2.substring(0, newnum2.length() - 1);
                mark--;
            }
        }
        System.out.println("Mod: " + num1);
        StringBuilder result = new StringBuilder();
        for (int i = 0; i < res.length; i++) {
            result.insert(0, res[i]);
        }
        return result.toString();
    }