java - 如何在 Java 中实现大整数减法？

Question

我想减去 2 个大整数并且不使用像 BigInteger 这样的 API，并自己实现求和运算。

我已经实现了，如下所示，我可以在不使用 BigInteger 的情况下添加 2 个大整数。

class BigIntAdd{
    public static void main(String args[]){
        String s1 = "7654729850328997631007285998163550104";
        String s2 = "5980139243970186632651869926335829102";
        add(s1, s2);
    }

    public static String add(String addend1, String addend2) {
        StringBuilder buf = new StringBuilder();
        for ( int i1 = addend1.length() - 1, i2 = addend2.length() - 1, carry = 0;
              i1 >= 0 || i2 >= 0 || carry != 0;
              i1--, i2-- ) {
            int digit1 = i1 < 0 ? 0 :
                         Integer.parseInt(Character.toString(addend1.charAt(i1)));
            int digit2 = i2 < 0 ? 0 :
                         Integer.parseInt(Character.toString(addend2.charAt(i2)));

            int digit = digit1 + digit2 + carry;
            if (digit > 9) {
                carry = 1;
                digit -= 10;
            } else {
                carry = 0;
            }

            buf.append(digit);
        }
        return buf.reverse().toString();
    }

我如何修改代码，使其可以减去 2 个大整数？

Answer 1

这是一个非常简单的 BigInteger 减法示例。提前抱歉，因为我使用字符数组而不是 String 来表示数字，但你可以明白这一点。

private static char[] subtractValue(char[] greater, char[] smaller) {
        char[] result = new char[greater.length];
        int index = 1;
        int carry = 0;
        int digit;

        // 1. subtract shorter part
        while (index <= smaller.length) {
                digit = Character.getNumericValue(greater[greater.length-index]) - Character.getNumericValue(smaller[smaller.length-index]) - carry;
                carry = digit < 0 ? 1 : 0;
                digit = digit + (carry == 1? 10 : 0);
                result[greater.length - index] = Character.forDigit(digit, 10);
                index++;
        }

        // 2. carry rippling
        while (index <= greater.length) {
                digit = Character.getNumericValue(greater[greater.length-index]) - carry;
                carry = digit < 0 ? 1 : 0;
                digit = digit + (carry == 1 ? 10 : 0);
                result[greater.length - index] = Character.forDigit(digit, 10);
                index++;
        }

        // 3. trim out trailing zeros
        int i;
        for(i = 0; i < result.length - 1 && result[i] == '0'; i++) {
        }
        return Arrays.copyOfRange(result, i, result.length);
}

你可以这样调用它:

char[] bigger = new char[]{'7', '7', '8'};
char[] smaller = new char[]{'1', '2', '3'};
String result = Arrays.toString(subtractValue(bigger, smaller));
System.out.println(result);

希望对您有所帮助!

编辑

1。减去较短的部分

这段代码简单地从greater中减去smaller的每个i位，如果有进位，它会传播进位对于 (i + 1) 个数字。

 2 1 0
 1 2 3
 -----
 0 8 7

2。携带涟漪

如果上一步留下任何进位，则此部分减去，并在需要时传播新的进位，直到进位变为零。

In (1) part, we did - 
2 0 0
0 7 8
------
0 2 2

Now, we have still carry 1 left from (1) to subtract

2 0 0
1
-----
1 2 2

3。修剪尾随零

此部分删除尾随零。

1 2 3
1 2 1
-----
0 0 2

After trimming zeros

2