[[TOC]]
前言
高精度算法,又叫做大数运算,有些时候我们写的题目需要对非数字大的数字进行运算.int和long 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/