0x00-基础算法-(4)-高精度 - Be Grinder,for Better

高精度运算

高精度运算是位运算中一种比较广泛应用，其中的进位/借位机制很容易拓展到N进制计算。

只有C++需要注意高精度的问题，Java有大整数类BigInteger，Python的范围默认无限大。

Step1:大整数存储 (用vector)

Step2:代码模拟人工计算

大整数存储

倒着表示：[0]下标存储个位=>方便需要进位时，push_back()直接移位覆盖

int main() {
    string a, b;
    vector<int> A, B;
    
    cin >> a >> b; 
    
    // a = "123456"
    // A[6, 5, 4, 3, 2, 1] 
    for (int i = a.size() - 1; i >= 0; i --) A.push_back(a[i] - '0'); 
    for (int i = b.size() - 1; i >= 0; i --) B.push_back(b[i] - '0');
    
    return 0;
}

模拟人工运算

注意以下默认传入参数A和B都是正整数(不带±号)，也可以理解为绝对值的运算。

|A| + |B|、 |A| - |B|、|A| * |b|、|A| / |b|

模拟运算过程中最主要的是理解进位/借位机制的模拟写法。

A + B

高精度正整数A + 高精度正整数B，返回和C

加法的位运算结果范围 $t\in[0,20)$

再用 $t$ 来表示位运算的进位:

当 $t \in [0,10)$ ，t / 10为0，不进位，当位运算结果t(也可以写成(t % 10))；
当 $t \in [10,20)$ ，t / 10为1，进位，当位运算结果t % 10.

#include <vector>
#include <iostream>

using namespace std;

// A + B
vector<int> add(const vector<int>& A, const vector<int>& B) {
	vector<int> C;
    
    int t = 0; // 进位
    for (int i = 0; i < A.size() || i < B.size(); i ++) {
        if (i < A.size()) t += A[i];
        if (i < B.size()) t += B[i];
        
        C.push_back(t % 10);
        // 标记本次运算是否进位，用于下一位运算
        t /= 10;
    }
    
    // 最高位进位, 如:11 + 99 = 110
    if(t) C.push_back(t); 
    
    return C;
}

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

A - B

高精度正整数A - 高精度正整数B，返回差C

减法的位运算结果范围 $t\in(-10,10)$

再用 $t$ 来表示位运算的借位:

当 $t \in [0,10)$ ，t > 0，无需借位，当位运算结果t(也可以写成(t + 10) % 10);
当 $t \in (-10, 0)$ ，t < 0，需要借位，当位运算结果(t + 10) % 10.

#include <vector>
#include <iostream>

using namespace std;

// 判断是否有 A >= B
bool cmp(const vector<int>& A, const 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; 
}

// A - B : 默认传入的A >= B, 如果A < B，算 -(sub(B, A))
vector<int> sub(vector<int> &A, vector<int> &B) {
    vector<int> C;
    
    int t = 0; // 借位
    for (int i = 0; i < A.size() || i < B.size(); i ++) {
        if (i < A.size()) t = A[i] - t;
        if (i < B.size()) t -= B[i];
        
        // C.push_back((t + 10) % 10); // 可以从if-else中提出来
        // 标记本次运算是否借位，用于下一位运算
        if (t > 0) {
            C.push_back((t + 10) % 10);
            t = 1;
        }
        else {
            C.push_back(t); // 也可以写成C.push_back((t + 10) % 10);
            t = 0;
        }
    }
    
    // 去掉高位的多个0[只保留个位的0], 如:123 - 120 = 003
    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.size() - 1; i >= 0; i --) A.push_back(a[i] - '0'); 
    for (int i = b.size() - 1; i >= 0; i --) B.push_back(b[i] - '0');
    
    if (cmp(A, B)) {
        // A > B
        auto C = sub(A, B);
        for (int i = C.size() - 1; i >= 0; i --) printf("%d", C[i]);
	} 
    else {
        // B > A
        auto C = sub(B, A);
        printf("-");
        for (int i = C.size() - 1; i >= 0; i --) printf("%d", C[i]);
	}
    
    return 0;
}

A * b

高精度正整数A * 低精度正整数b，返回乘积C

考虑思路和A + B差不多

#include <vector>
#include <iostream>

using namespace std;

// A * b
vector<int> mul(vector<int> &A, int b) {
    vector<int> C;
    
    int t = 0;
    // 当进位t为0时停止循环，可以省去后面的[最高位进位]和[去掉高位的多个0]的操作
    // for(int i = 0; i < A.size() || t; i ++) ，
    for(int i = 0; i < A.size(); i ++) {
        t += A[i] * b;
        C.push_back(t % 10);
        t /= 10;
	}
    
    // 最高位进位
    if(t) C.push_back(t);
    // 去掉高位的多个0[只保留个位的0], 如:12345 * 0 = 00000;
    while(C.size() > 1 && C.back() == 0) C.pop_back();
    
    return C;
}

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

A / b

高精度正整数A / 低精度正整数b，返回商C和余数r

注意人工算除法是从最高位开始除的，
因此模拟时for循环要从后往前，并且结束后为了保持大整数存储的一致性，要reverse()反转C

#include <vector>
#include <iostream>
#include <algorithm>

using namespace std;

// A / b, 商是C, 余数是r
vector<int> div(vector<int> &A, int b, int &r) {
    vector<int> C;
    
    r = 0;// 因为C++函数只能返回一个值，所以使用传引用&r来影响r的值
    for (int i = A.size() - 1; i >= 0; i --) {
        r = r * 10 + A[i];
        C.push_back(r / b);
        r %= b;
    }
    
    reverse(C.begin(), C.end());
    // 去掉高位的多个0[只保留个位的0], 如:100 / 19 = 005...5
    while(C.size() > 1 && C.back() == 0) C.pop_back();
    
    return C;
}

int main() {
    string a;
    int b;
    
    cin >> a >> b;
    
    vector<int> A;
    for (int i = a.size() - 1; i >= 0; i --) A.push_back(a[i] - '0');
    
    int r;//余数 
    auto C = div(A, b, r);
    
    // 商
    for (int i = C.size() - 1; i >= 0; i --) printf("%d", C[i]);
    
    cout << endl;
    cout << r << endl;
    
    return 0;
}

A ^ b

即高精度快速幂，要先实现一个高精度A*高精度B，然后套普通快速幂的板子

// O(nm)
// C = A * B, A >= 0, B >= 0
vector<int> mul(const vector<int> &A, const vector<int> &B) {
    vector<int> C(A.size() + B.size());
    for (int i = 0; i < A.size(); i++) {
        for (int j = 0; j < B.size(); j++) {
            C[i + j] += A[i] * B[j];
        }
    }
    int t = 0;
    for (int i = 0; i < C.size(); i++) {
        t += C[i];
        C[i] = t % 10;
        t /= 10;
    }
    while (C.size() > 1 && C.back() == 0) C.pop_back();
    return C;
}

// 高精度x^N
vector<int> fast_pow(vector<int> x, int N) {
	vector<int> res; res.push_back(1); // 初始1

	for (; N; N = N >> 1) {
		if (N & 1) {
			res = mul(res, x);
		}
		x = mul(x, x);         // 倍增
	}

	return res;
}

P1009.阶乘之和

时间复杂度分析

${n}$ 取max(A.size(), B.size())

A + B : $O(n)$

A - B : $O(n)$

A * b : $O(n)$

A / b : $O(n)$ ，尽管有reverse()函数，但是reverse也是 $O(n)$ 的。

练习eg:

Acwing-124.数的进制转换

补充一个:string去除前导零的操作

如果给你一个用string从高位到低位存储的大数，怎么去把字符串中多余的前导零去掉。

主要是0000000000102 和00102去除掉前导零后，是相同的数102。

string trim(string s) {
    // 由于是前导0， 因此最后一位不判断
	int i = 0;
    while (i < s.size() - 1 && s[i] == '0') {
        i ++;
    }
    return s.substr(i);
}

数据结构与算法

Algorithm Template C++

本博客所有文章均采用 CC BY-NC-SA 4.0 协议，禁止商用，转载请注明出处！

0x00-基础算法-(5)-前缀和&差分上一篇

0x00-基础算法-(3)-离散化下一篇