[[TOC]]

前言

高精度算法,又叫做大数运算,有些时候我们写的题目需要对非数字大的数字进行运算.intlong long哪怕是__int128也存不下.

加法

注意: 这个算法不会计算负值,默认所有数都是正数

版本1

#include <iostream>
#include <cstring>
using namespace std;
const int maxn = 1e5+5;

//bn = big_number
struct bn { 
    int len;
    int a[maxn];

    //索引
    int & operator[](int id) { return a[id]; }

    //赋值
    bn & operator=(int b) {
        len = 0;
        while( b) {
            a[len++] = b % 10;
            b /= 10;
        }
    }

    //赋值
    bn & operator=(const bn & b) {
        len = b.len;
        for (int i = 0; i < len; ++i) a[i] = b.a[i];
    }
};

// a = b+c
void bn_add( bn & a,bn &b ,bn & c) {
    //清空a的值
    memset(&a,0,sizeof(a));
    a.len = max(b.len,c.len);
    for(int i =0 ;i<a.len;i++) {
        a[i] += b[i] + c[i];
        a[i+1] = a[i] /10;
        a[i] %= 10;
    }
    if(a[a.len]) a.len++;
}

void bn_print(bn & a) {
    for(int i = a.len-1 ;i>=0;i--) cout << a[i];
}

void str2bn(char * a,bn &b) {
    b.len = strlen(a);
    int cnt = 0;
    for(int i=b.len-1;i>=0;i--) b[cnt++] = a[i] - '0';
}

// a = b
void copy( bn & a,bn &b) {
    a.len = b.len;
    for(int i = 0;i < a.len ;++i ) a[i] = b[i];
}

版本2

#include <iostream>
#include <string>
#include <cstring>
using namespace std;

struct BigInt {
    std::string num;
    BigInt() = default;

    BigInt(const char *s)  {
        num.clear();
        for (int i = strlen(s) - 1; i >= 0;i--){
            num.push_back(s[i] - '0');
        }
    }
    BigInt(std::string & s) : BigInt(s.c_str())  {}

    BigInt(const BigInt & b) : num(b.num) {}
    BigInt(BigInt && b) : num(std::move(b.num)) {}

    int size () const { return num.size(); }

    BigInt& operator=(const BigInt & a){
        num = a.num;
        return *this;
    }

    friend BigInt& operator+=(BigInt &a ,const BigInt & b) {
        int n = a.size();
        int m = b.size();
        if( m > n)
            a.num.append(m - n, 0);
        int carry = 0,s = 0; //进位
        for (int i = 0; i < n; i++)
        {
            if( i < m)
                s = a.num[i] + b.num[i] + carry;
            else
                s = a.num[i] + carry;
            carry = s / 10;
            a.num[i] = s % 10;
        }
        if( carry)
            a.num.push_back(carry);
        return a;
    }

    friend BigInt operator+(const BigInt & a , const BigInt & b ) {
        BigInt t;
        t = a;
        t += b;
        return t;
    }

    friend std::ostream & operator<<(std::ostream & out,const BigInt & a) {
        //倒过来输出
        int size = a.num.length();
        for (int i = size-1; i >=0;i--)
            out << int(a.num[i]);
        return out;
    }
};

char a[10000];
int main()
{
    cin >> a;
    BigInt b1(a);
    cin >> a;
    BigInt b2(a);

    BigInt b3 = b1 + b2;
    cout << b3 << endl;

    return 0;
}

参考 https://www.geeksforgeeks.org/bigint-big-integers-in-c-with-example/