高精度运算：大数加减乘除

一、为什么需要高精度

编程语言内置的整数类型有上限（Java long 最大约 9.2×10^18）。当数字超过这个范围时（如 100 位的大数），必须用数组/字符串模拟竖式运算。

面试高频题：

题目	操作	难度
LC 415. 字符串相加	大数加法	Easy
LC 43. 字符串相乘	大数乘法	Medium
LC 2. 两数相加	链表加法	Medium
LC 67. 二进制求和	二进制加法	Easy
剑指 16. 数值的整数次方	快速幂	Medium

二、高精度加法

2.1 核心思路

模拟竖式：从最低位开始逐位相加，维护进位。

    9 9 9
+     1 1
---------
  1 0 1 0

2.2 模板

String addStrings(String num1, String num2) {
    StringBuilder sb = new StringBuilder();
    int i = num1.length() - 1, j = num2.length() - 1, carry = 0;

    while (i >= 0 || j >= 0 || carry > 0) {
        int sum = carry;
        if (i >= 0) sum += num1.charAt(i--) - '0';
        if (j >= 0) sum += num2.charAt(j--) - '0';
        sb.append(sum % 10);
        carry = sum / 10;
    }
    return sb.reverse().toString();
}

ListNode addTwoNumbers(ListNode l1, ListNode l2) {
    ListNode dummy = new ListNode(0), cur = dummy;
    int carry = 0;
    while (l1 != null || l2 != null || carry > 0) {
        int sum = carry;
        if (l1 != null) { sum += l1.val; l1 = l1.next; }
        if (l2 != null) { sum += l2.val; l2 = l2.next; }
        cur.next = new ListNode(sum % 10);
        carry = sum / 10;
        cur = cur.next;
    }
    return dummy.next;
}

// 假设 a >= b >= 0，返回 a - b
String subtract(String a, String b) {
    StringBuilder sb = new StringBuilder();
    int i = a.length() - 1, j = b.length() - 1, borrow = 0;

    while (i >= 0) {
        int diff = (a.charAt(i--) - '0') - borrow;
        if (j >= 0) diff -= (b.charAt(j--) - '0');
        if (diff < 0) { diff += 10; borrow = 1; }
        else borrow = 0;
        sb.append(diff);
    }
    // 去前导零
    while (sb.length() > 1 && sb.charAt(sb.length() - 1) == '0')
        sb.deleteCharAt(sb.length() - 1);
    return sb.reverse().toString();
}

String multiply(String num1, String num2) {
    if ("0".equals(num1) || "0".equals(num2)) return "0";
    int m = num1.length(), n = num2.length();
    int[] res = new int[m + n];

    for (int i = m - 1; i >= 0; i--) {
        for (int j = n - 1; j >= 0; j--) {
            int mul = (num1.charAt(i) - '0') * (num2.charAt(j) - '0');
            int p1 = i + j, p2 = i + j + 1;
            int sum = mul + res[p2];
            res[p2] = sum % 10;
            res[p1] += sum / 10;
        }
    }

    StringBuilder sb = new StringBuilder();
    for (int d : res) {
        if (!(sb.length() == 0 && d == 0)) sb.append(d);
    }
    return sb.length() == 0 ? "0" : sb.toString();
}

// 大数 num ÷ 小数 divisor，返回商和余数
String divide(String num, int divisor) {
    StringBuilder quotient = new StringBuilder();
    int remainder = 0;
    for (int i = 0; i < num.length(); i++) {
        int cur = remainder * 10 + (num.charAt(i) - '0');
        quotient.append(cur / divisor);
        remainder = cur % divisor;
    }
    // 去前导零
    String result = quotient.toString().replaceFirst("^0+", "");
    return result.isEmpty() ? "0" : result;
}

String addBinary(String a, String b) {
    StringBuilder sb = new StringBuilder();
    int i = a.length() - 1, j = b.length() - 1, carry = 0;
    while (i >= 0 || j >= 0 || carry > 0) {
        int sum = carry;
        if (i >= 0) sum += a.charAt(i--) - '0';
        if (j >= 0) sum += b.charAt(j--) - '0';
        sb.append(sum % 2);
        carry = sum / 2;
    }
    return sb.reverse().toString();
}

高精度运算：大数加减乘除

一、为什么需要高精度

二、高精度加法

2.1 核心思路

2.2 模板

一、为什么需要高精度

二、高精度加法

2.1 核心思路

2.2 模板

2.3 链表版（LC 2）

三、高精度减法

四、高精度乘法

4.1 核心思路

4.2 模板

4.3 关键洞察

五、高精度除法（大数 ÷ 小数）

六、二进制加法（LC 67）

七、面试注意事项

相关教程