C++实现正整数的高精度计算

高精度计算本质上就是模拟列竖式计算，这里只讨论正整数运算。

文章目录

• C++实现正整数的高精度计算
• • 1.高精度加法
  • • 一、用字符串模拟列竖式运算
    • 二、用模板类vector模拟列竖式计算
  • 2.高精度减法
  • 3.高精度乘法
  • • 一、高精度乘低精度
    • 二、高精度乘高精度
  • 4.高精度除法

1.高精度加法

在高精度四则运算中，高精度加法是最为简单的一种，所以将它放在第一个。高精度加法有两种实现方式。

一、用字符串模拟列竖式运算

string add(string a, string b)
{
    if (a.size() < b.size()) return add(b, a);
    string c;												 //结果字符串
    reverse(a.begin(), a.end()), reverse(b.begin(), b.end());//将a、b反转

    int t = 0;
    for (int i = 0; i < a.size() || t; i++) 				   //模拟列竖式计算
    {
        if (i < a.size())
        {
            t += a[i] - '0';
            if (i < b.size()) t += b[i] - '0';
        }
        c += char(t % 10 + '0');
        t /= 10;
    }

    reverse(c.begin(), c.end());								//结果字符串反转
    return c;
}

注：使用reverse函数时要包含头文件algorithm

二、用模板类vector模拟列竖式计算

函数部分：

vector<int> add(vector<int> a, vector<int> b)
{
	if (a.size() < b.size()) return add(b, a);
	vector<int>c;

	int t = 0;
	for (int i = 0; i < a.size() || t; i++)
	{
		if (i < a.size())
		{
			t += a[i];
			if (i < b.size()) t += b[i];
		}
		c.push_back(t % 10);
		t /= 10;
	}

	return c;
}

输入部分：

vector<int> 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--) cout << C[i];
cout << endl;

注：使用模板类vector须包含头文件vector

2.高精度减法

高精度减法需要考虑前导零和正负数问题。这里就用vector模板类来写，当然也可以用string来写，我这里不做演示了。

vector<int> sub(vector<int> a, vector<int> b)
{
    vector<int>c;
    int t = 0;
    for (int i = 0; i < a.size() || t; i++)
    {
        int now = a[i] - t;
        if (i < b.size()) now -= b[i];
        c.push_back((now + 10) % 10);
        if (now < 0) t = 1;
        else t = 0;
    }
    while (c.size() > 1 && c.back() == 0) c.pop_back();
    return c;
}

输入时的注意事项

 string a, b;
 cin >> a >> b;
 vector<int>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 (camp(A, B))
 {
     auto c = sub(A, B);
     for (int i = c.size() - 1; i >= 0; i--) cout << c[i];
     cout << endl;
 }
 else
 {
     auto c = sub(B, A);
     cout.put('-');
     for (int i = c.size() - 1; i >= 0; i--) cout << c[i];
     cout << endl;
 }

cmap函数

bool camp(vector<int> a, vector<int> b)
{
    if (a.size() != b.size()) return a.size() > b.size();
    else
    {
        for (int i = a.size() - 1; i >= 0; i--)
            if (a[i] != b[i])
                return a[i] > b[i];
    }
    return 1;
}

注：cmap函数用来判断两数大小的函数

3.高精度乘法

高精度乘法分为两种，分别是高精度乘低精度和高精度乘高精度。但究其本质都是模拟列竖式运算。

一、高精度乘低精度

这个比较简单，理解了高精度加法再理解这个很简单。输入输出记住要将顺序颠倒一下就是了。

函数部分：

vector<int> mul(vector<int>a, int b)
{
	vector<int>ans;
	int t = 0;
	for (int i = 0; i < a.size() || t; i++)
	{
		if(i < a.size())t += a[i] * b;
		ans.push_back(t % 10);
		t /= 10;
	}
	return ans;
}

二、高精度乘高精度

高精度乘高精度就是一位一位地去模拟列竖式，以及结合高精度加法，还要考虑移位问题，较为繁琐。

以下是函数部分

vector<int> mul(vector<int>a, vector<int> b)
{
	vector<int >ans;
	for (int i = 0; i < a.size(); i++)
	{
		int t = 0;
		vector<int>n;
		for (int j = 0; j < i; j++)n.push_back(0);//列竖式中要往前移一位，这里通过在数的后边加0来实现，由于数是倒过来
		for (int j = 0; j < b.size() || t; j++)	  //的，就在它的左边加0。
		{
			if(j < b.size())t += a[i] * b[j];
			n.push_back(t % 10);
			t /= 10;
		}
		ans = add(ans, n);
	}
	return ans;
}

这里的add函数是高精度加法函数，直接用vector模板类的高精度加法就可以了。

4.高精度除法

这是高精度除以低精度的函数写法，C是结果的商，r是结果的余数。这个比较简单，注意去除前导零和reverse函数的头文件cstring就可以了。

vector<int> div(vector<int> A, int b,int& r)
{
	vector<int>C;
	r = 0;
	for (int i = A.size() - 1; i >= 0; i--)
	{
		r = r * 10 + A[i];
		C.push_back(r / b);
		r = r % b;
	}
	reverse(C.begin(), C.end());
	while (C.size() > 1 && C.back() == 0)C.pop_back();
	return C;
}