imicola's Blog

高精度

5分钟阅读

模拟 高精度

高精度

  • 一般而言，在long long 格式下的字符占用有8个字节，其范围是-2^63^~2^63^-1(19位数)这个区间，那么，超过这个区间的计算我们又该如何进行呢？

1 高精度加法

  • 在进行超过19位数相加的大数加法的时候，我们可以模拟竖式加法的原理，对数组进行操作
    如图
  1. 使用字符串获取大数字
  2. 将字符串的数字提取出来逆序储存在数组中
  3. 对数组中的数组做加法并存储到另一个数组中
  4. 逆序输出数组
#include<bits/stdc++.h>
using namespace std;
 
int main()
{
    string s1,s2;
    int a1[210],a2[210],a3[210] = {0};
    getline(cin,s1);
    getline(cin,s2);
    for (size_t i = 0; i < s1.size(); i++)
    {
        a1[s1.size()-i-1] = s1[i] - '0';
    }
    for (size_t i = 0; i < s2.size(); i++)
    {
        a2[s2.size()-i-1] = s2[i] - '0';
    }
    int len = max(s1.size(),s2.size()); 
    for (size_t i = 0; i < len;i++)
    {
        a3[i] = a1[i] + a2[i];
    }
    for (size_t i = 0; i < len; i++)
    {
        if (a3[i] >= 10)
        {
            a3[i + 1] = a3[i]/10;
            a3[i] = a3[i]%10;
        }
    }
    if (a3[len] != 0)
    {
        len++;
    }
    for (int i = len - 1; i >= 0; i--)
    {
        cout << a3[i];
    }
    return 0;
}
  • 更好用的字符串 string类型的高精度
string largeadd(string& a, string& b)
{
    if (a.size() <= b.size()) swap(a, b);
    int p = 0;
    for (size_t i = 0; i < b.size(); i++) {
        int ai = a[a.size() - i - 1] - '0';
        int bi = b[b.size() - i - 1] - '0';
        int sum = ai + bi + p;
        if (sum >= 10) {
            p = 1;
            sum -= 10;
        } else p = 0;
        a[a.size() - 1 - i] = sum + '0';
    }
    for (size_t i = b.size(); i < a.size(); i++) {
        int ai = a[a.size() - i - 1] - '0';
        if (ai == '9' && p == 1) {
            a[a.size() - i - 1] = '0';
        } else {
            a[a.size() - i - 1] = ai + p + '0';
            p = 0;
        }
    }
    if (p == 1) a.insert(a.begin(), '1');
    return a;
}

2 高精度减法

  • 与加法类似，主要是注意借位与进位的不同
  • 负数的处理
string largemin(string a, string b)
{
    int flag = 0;
    if (b.size() >= a.size()&& b >= a) {
        swap(a, b);
        flag = 1;
    }
    int p = 0;
    for (size_t i = 0; i < b.size(); i++) {
        int ai = a[a.size() - 1 - i] - '0';
        int bi = b[b.size() - 1 - i] - '0';
        int diff = ai - bi - p;
        if (diff < 0) {
            p = 1;
            diff += 10;
        } else p = 0;
        a[a.size() - i - 1] = diff + '0';
    }
    for (size_t i = b.size(); i < a.size(); i++) {
        int ai = a[a.size() - i - 1] - '0';
        if (ai == 0 && p == 1) {
            a[a.size() - i - 1] = '9';
        } else {
            a[a.size() - i - 1] = ai - p + '0';
            p = 0;
        }
    }
    while (*a.begin() == '0' && a.size() > 1)
        a.erase(a.begin());
    if (flag) a.insert(a.begin(), '-');
    return a;
}

3 高精度乘法

Tip

对于乘法来说，高精度的最佳计算思维就是将两个数拆分，用一个数的个十百位依次去乘以另一个数

拿我们常用的，主要的步骤有以下几点：

  1. 字符串化数字，倒置字符串
  2. 两位相乘，计算结果与储存位数
  3. 数组变字符串
//#pragma GCC optimize(2)
#include <bits/stdc++.h>
#define endl '\n'
using namespace std;
 
string largemuiti(string a, string b)
{
    if (a == "0" || b == "0") return "0";
    int len1 = a.size();
    int len2 = b.size();
    vector<int> result(len1 + len2, 0);
    for (int i = len1 - 1; i >= 0; i--) {
        for (int j = len2 - 1; j >= 0; j--) {
            int mult = (a[i] - '0') * (b[j] - '0');
            int sum = result[i + j + 1] + mult;
            result[i + j + 1] = sum % 10;
            result[i + j] += sum / 10;
        }
    } 
    string res = "";
    for (size_t i = 0; i < result.size(); i++) {
        if (!(result[i] == 0 && res.empty())) {
            res += to_string(result[i]);
        }
    }
    return res;
}
 
int main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cout << largemuiti("123", "234");
    return 0;
}

关系图谱