高精度减法

一、算法思想

使用数组来存储大整数，为了方便处理进位，可以按照由低位到高位的顺序存储。

定义被减数 $A$，减数 $B$，以及低位对当前位的进位 $t$，那么

• 当 $A_i - B_i - t \ge 0$ 时，当前位结果为 $A_i - B_i - t$，同时，$t$ 更新为 $0$；
• 当 $A_i - B_i - t \lt 0$ 时，当前位结果为 $A_i - B_i + 10 - t$，同时，$t$ 更新为 $1$。

二、算法模板

C++

// C = A - B, 满足A >= B, A >= 0, B >= 0
vector<int> sub(vector<int> &A, vector<int> &B)
{
    vector<int> C;
    
    int t = 0;
    for (int i = 0; i < A.size(); i++) {
        t = A[i] - t;
        if (i < B.size()) t -= B[i];
        C.push_back((t + 10) % 10);
        t = t < 0 ? 1 : 0;
    }
    
    // 去除前导 0
    while (C.size() > 1 && C.back() == 0) C.pop_back();
    
    return C;
}

Go

func sub(A, B []int) (C []int) {
    t := 0
    for i := 0; i < len(A); i++ {
        t = A[i] - t
        if i < len(B) {
            t -= B[i]
        }
        C = append(C, (t+10)%10)
        if t < 0 {
            t = 1
        } else {
            t = 0
        }
    }
    // 去除前导 0
    for len(C) > 1 && C[len(C)-1] == 0 {
        C = C[:len(C)-1]
    }
    return
}

三、代码实战

AcWing 0792

---

题目：高精度减法

给定两个正整数（不含前导 $0$），计算它们的差，计算结果可能为负数。

输入格式

共两行，每行包含一个整数。

输出格式

共一行，包含所求的差。

数据范围

$1\le \text{整数长度} \le 10^5$

输入样例：

32

11

输出样例：

21

解答代码：

#include <iostream>
#include <vector>

using namespace std;

bool cmp(vector<int> &A, vector<int> &B)
{
    if (A.size() != B.size()) return A.size() > B.size();
    for (int i = A.size() - 1; i >= 0; i--) {
        if (A[i] != B[i]) return A[i] > B[i];
    }
    return true;
}

vector<int> sub(vector<int> &A, vector<int> &B)
{
    vector<int> C;
    
    int t = 0;
    for (int i = 0; i < A.size(); i++) {
        t = A[i] - t;
        if (i < B.size()) t -= B[i];
        C.push_back((t + 10) % 10);
        t = t < 0 ? 1 : 0;
    }
    
    // 去除前导 0
    while (C.size() > 1 && C.back() == 0) C.pop_back();
    
    return C;
}

int main()
{
    string a, b;
    vector<int> A, B;
    
    cin >> a >> b;
    for (int i = a.length() - 1; i >= 0; i--) A.push_back(a[i] - '0');
    for (int i = b.length() - 1; i >= 0; i--) B.push_back(b[i] - '0');
    
    if (cmp(A, B)) {
        vector<int> C = sub(A, B);
        for (int i = C.size() - 1; i >= 0; i--) printf("%d", C[i]);
    } else {
        vector<int> C = sub(B, A);
        printf("-");
        for (int i = C.size() - 1; i >= 0; i--) printf("%d", C[i]);
    }
    
    return 0;
}

package main

import (
    "bufio"
    . "fmt"
    "io"
    "os"
)

// 高精度减法
// C = A - B，满足 A >= B, A >= 0, B >= 0
func sub(A, B []int) (C []int) {
    t := 0
    for i := 0; i < len(A); i++ {
        t = A[i] - t
        if i < len(B) {
            t -= B[i]
        }
        C = append(C, (t+10)%10)
        if t < 0 {
            t = 1
        } else {
            t = 0
        }
    }
    // 去除前导 0
    for len(C) > 1 && C[len(C)-1] == 0 {
        C = C[:len(C)-1]
    }
    return
}

// 比较 A 和 B 的大小关系，A >= B 时返回 true
func cmp(A, B []int) bool {
    if len(A) != len(B) {
        return len(A) > len(B)
    }
    for i := len(A) - 1; i >= 0; i-- {
        if A[i] != B[i] {
            return A[i] > B[i]
        }
    }
    return true
}

func run(_r io.Reader, out io.Writer) {
    in := bufio.NewReader(_r)

    var a, b string
    Fscan(in, &a, &b)

    var A, B []int
    for i := len(a) - 1; i >= 0; i-- {
        A = append(A, int(a[i]-'0'))
    }
    for i := len(b) - 1; i >= 0; i-- {
        B = append(B, int(b[i]-'0'))
    }

    var C []int
    if cmp(A, B) {
        C = sub(A, B)
    } else {
        C = sub(B, A)
        Fprintf(out, "-")
    }
    for i := len(C) - 1; i >= 0; i-- {
        Fprintf(out, "%d", C[i])
    }
}

func main() {
    run(os.Stdin, os.Stdout)
}