每日算法 — 使用java实现高精度大整数：模拟竖式运算

问题描述

在Java中，long 类型的最大值约为 9 × 10^18，当需要处理更大的整数时（如100位、1000位甚至更多位的大数），基本数据类型无法满足需求。高精度计算（Big Integer）通过模拟人工竖式计算的方式，使用字符串或数组存储大数的每一位，实现任意精度整数的四则运算。

算法思路

存储方式

使用 int[] 或 ArrayList<Integer> 逆序存储每一位数字。例如数字 12345 存储为 [5, 4, 3, 2, 1]，这样个位对齐，便于从低位到高位逐位运算。

加法

从低位到高位逐位相加，处理进位。时间复杂度 O(max(n, m))。

减法

先比较大小，用大数减小数，从低位到高位逐位相减，处理借位。时间复杂度 O(max(n, m))。

乘法

模拟竖式乘法：结果的第 i+j 位由第一个数的第 i 位和第二个数的第 j 位相乘累加得到。时间复杂度 O(n × m)。

除法

使用试商法，从被除数的高位开始，逐位确定商的每一位。时间复杂度 O(n × m)。

Java实现

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class BigInteger {
    // 逆序存储：digits[0]是个位
    private List<Integer> digits;
    private boolean negative; // true表示负数

    public BigInteger(String num) {
        if (num == null || num.isEmpty()) {
            throw new IllegalArgumentException("Invalid number");
        }
        digits = new ArrayList<>();
        int start = 0;
        negative = false;

        if (num.charAt(0) == '-') {
            negative = true;
            start = 1;
        } else if (num.charAt(0) == '+') {
            start = 1;
        }

        // 去除前导零
        while (start < num.length() - 1 && num.charAt(start) == '0') {
            start++;
        }

        for (int i = num.length() - 1; i >= start; i--) {
            char c = num.charAt(i);
            if (c < '0' || c > '9') {
                throw new IllegalArgumentException("Invalid digit: " + c);
            }
            digits.add(c - '0');
        }

        if (digits.isEmpty()) {
            digits.add(0);
        }
        // 零的符号始终为正
        if (digits.size() == 1 && digits.get(0) == 0) {
            negative = false;
        }
    }

    private BigInteger(List<Integer> digits, boolean negative) {
        this.digits = new ArrayList<>(digits);
        this.negative = negative;
        normalize();
    }

    private void normalize() {
        while (digits.size() > 1 && digits.get(digits.size() - 1) == 0) {
            digits.remove(digits.size() - 1);
        }
        if (digits.size() == 1 && digits.get(0) == 0) {
            negative = false;
        }
    }

    public BigInteger abs() {
        return new BigInteger(digits, false);
    }

    public boolean isNegative() {
        return negative;
    }

    /**
     * 比较绝对值大小
     * @return 正数表示this大，负数表示other大，0表示相等
     */
    private int compareAbs(BigInteger other) {
        if (digits.size() != other.digits.size()) {
            return digits.size() - other.digits.size();
        }
        for (int i = digits.size() - 1; i >= 0; i--) {
            int diff = digits.get(i) - other.digits.get(i);
            if (diff != 0) return diff;
        }
        return 0;
    }

    /**
     * 加法：this + other
     */
    public BigInteger add(BigInteger other) {
        // 异号情况转化为减法
        if (negative && !other.negative) {
            BigInteger temp = new BigInteger(digits, false);
            return other.subtract(temp);
        }
        if (!negative && other.negative) {
            BigInteger temp = new BigInteger(other.digits, false);
            return subtract(temp);
        }

        // 同号：绝对值相加，符号不变
        List<Integer> result = new ArrayList<>();
        int carry = 0;
        int maxLen = Math.max(digits.size(), other.digits.size());

        for (int i = 0; i < maxLen; i++) {
            int a = i < digits.size() ? digits.get(i) : 0;
            int b = i < other.digits.size() ? other.digits.get(i) : 0;
            int sum = a + b + carry;
            result.add(sum % 10);
            carry = sum / 10;
        }
        if (carry > 0) {
            result.add(carry);
        }

        return new BigInteger(result, negative);
    }

    /**
     * 减法：this - other
     */
    public BigInteger subtract(BigInteger other) {
        // 异号情况转化为加法
        if (negative && !other.negative) {
            BigInteger temp = new BigInteger(digits, false).add(other);
            return new BigInteger(temp.digits, true);
        }
        if (!negative && other.negative) {
            BigInteger temp = new BigInteger(other.digits, false);
            return add(temp);
        }

        // 同号：绝对值相减
        int cmp = compareAbs(other);
        if (cmp == 0) {
            return new BigInteger("0");
        }

        boolean resultNegative = false;
        List<Integer> larger, smaller;
        if (cmp > 0) {
            larger = digits;
            smaller = other.digits;
            resultNegative = negative; // 同号，大减小，符号不变
        } else {
            larger = other.digits;
            smaller = digits;
            resultNegative = !negative; // 小减大，符号翻转
        }

        List<Integer> result = new ArrayList<>();
        int borrow = 0;
        for (int i = 0; i < larger.size(); i++) {
            int a = larger.get(i);
            int b = i < smaller.size() ? smaller.get(i) : 0;
            int diff = a - b - borrow;
            if (diff < 0) {
                diff += 10;
                borrow = 1;
            } else {
                borrow = 0;
            }
            result.add(diff);
        }

        return new BigInteger(result, resultNegative);
    }

    /**
     * 乘法：this × other
     */
    public BigInteger multiply(BigInteger other) {
        if ((digits.size() == 1 && digits.get(0) == 0) ||
            (other.digits.size() == 1 && other.digits.get(0) == 0)) {
            return new BigInteger("0");
        }

        List<Integer> result = new ArrayList<>(Collections.nCopies(digits.size() + other.digits.size(), 0));

        for (int i = 0; i < digits.size(); i++) {
            int carry = 0;
            for (int j = 0; j < other.digits.size() || carry > 0; j++) {
                long product = result.get(i + j)
                    + (long) digits.get(i) * (j < other.digits.size() ? other.digits.get(j) : 0)
                    + carry;
                result.set(i + j, (int) (product % 10));
                carry = (int) (product / 10);
            }
        }

        boolean resultNegative = negative != other.negative;
        return new BigInteger(result, resultNegative);
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        if (negative) {
            sb.append('-');
        }
        for (int i = digits.size() - 1; i >= 0; i--) {
            sb.append(digits.get(i));
        }
        return sb.toString();
    }

    public static void main(String[] args) {
        // 加法测试
        BigInteger a = new BigInteger("12345678901234567890");
        BigInteger b = new BigInteger("98765432109876543210");
        System.out.println(a + " + " + b + " = " + a.add(b));

        // 减法测试
        BigInteger c = new BigInteger("10000000000000000000");
        BigInteger d = new BigInteger("1");
        System.out.println(c + " - " + d + " = " + c.subtract(d));

        // 大数乘法测试
        BigInteger e = new BigInteger("123456789");
        BigInteger f = new BigInteger("987654321");
        System.out.println(e + " × " + f + " = " + e.multiply(f));

        // 验证：与Java内置BigInteger对比
        java.math.BigInteger jA = new java.math.BigInteger("12345678901234567890");
        java.math.BigInteger jB = new java.math.BigInteger("98765432109876543210");
        System.out.println("\nJava内置验证：" + jA.add(jB));
    }
}

扩展：阶乘计算

public class Factorial {
    /**
     * 计算n的阶乘（使用自定义BigInteger）
     */
    public static BigInteger factorial(int n) {
        if (n < 0) {
            throw new IllegalArgumentException("n must be non-negative");
        }
        BigInteger result = new BigInteger("1");
        for (int i = 2; i <= n; i++) {
            result = result.multiply(new BigInteger(String.valueOf(i)));
        }
        return result;
    }

    public static void main(String[] args) {
        for (int n : new int[]{10, 20, 30, 50, 100}) {
            System.out.println(n + "! = " + factorial(n));
        }
    }
}

复杂度分析

实际应用

1. 密码学：RSA、ECC等算法需要处理数百位甚至上千位的大整数
2. 科学计算：天文学、量子物理中的高精度数值计算
3. 组合数学：大数阶乘、组合数计算
4. 竞赛编程：处理超出long范围的整数运算

总结

高精度计算是算法基础中的基础。通过模拟人工竖式运算，用数组逆序存储每一位，实现了任意精度整数的四则运算。理解高精度算法的实现原理，不仅有助于解决大数运算问题，更能加深对进位、借位等基本运算本质的理解。在实际工程中，推荐使用Java内置的 java.math.BigInteger，但在竞赛或面试中，手写实现仍是重要的基本功。