高精度四则运算

全篇写得有点简陋，可能需要有一定基础才能看懂，主要是自己复习算法的过程中记录一下，复习&熟悉一下高精度。

高精度加法

Q：为什么是逆序读入大数字？
A：我们在进行加法的时候是从个位数（最右侧的数字）开始，而数组是从首位加到末尾（从左往右），所以个位对应数组的首位。

vector<int> add(vector<int> &A,vector<int> &B)
{
	vector<int> C;
	int t=0; 
	for(int i=0;i<A.size() || i<B.size() || t;i++)
	{
		if(i<A.size()) t+=A[i];
		if(i<B.size()) t+=B[i];
		C.push_back(t%10);
		//t>=10，为1，进位；t<10，为0，不进位
		t/=10;   
	} 
	if(t) 
		C.push_back(1);  
	return C;
}

测试代码：

#include <iostream>
#include <vector>

using namespace std;

vector<int> add(vector<int> &A, vector<int> &B)
{
    vector<int> ret;
    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];
        ret.push_back(t % 10);
        t /= 10;
    }
    if (t)
        ret.push_back(1);
    return ret;
}

int main()
{
    string a = "123456789", b = "987654321";
    // 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');

    vector<int> ret = add(A, B);

    for (int i = ret.size() - 1; i >= 0; i--)
        cout << ret[i];
    return 0;
}

高精度减法

和加法差不多的思想。多了一个正负号的判断，这里就直接上完整代码了。

#include <iostream>
#include <vector>

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

// C=A-B
vector<int> sub(const vector<int> &A, const vector<int> &B) {
  vector<int> ret;
  int borrow = 0;  // 借位

  for (int i = 0; i < A.size(); ++i) {
    int a = A[i] - borrow;
    int b = (i < B.size()) ? B[i] : 0;

    if (a < b) {
      a += 10;
      borrow = 1;
    } else {
      borrow = 0;
    }

    ret.push_back(a - b);
  }

  // 移除前导零
  while (ret.size() > 1 && ret.back() == 0) {
    ret.pop_back();
  }

  return ret;
}

int main() {
  string a = "9223372036854775807", b = "9223372036854775807";
  vector<int> A, B;

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

  if (cmp(A, B)) {
    vector<int> C = sub(A, B);
    for (int i = C.size() - 1; i >= 0; i--) cout << C[i];
  } else  // 若A<B时，用B-A再在前面加个负号
  {
    vector<int> C = sub(B, A);
    cout << "-";
    for (int i = C.size() - 1; i >= 0; i--) cout << C[i];
  }
  return 0;
}

高精度乘法

写得有点抽象了，有问题的话甩给gpt自己可以仔细琢磨一下，然后用纸笔模拟一下就能理解了。这里不做过多解释。就是拿A的每一位去乘B的所有位。
如：A是123，B是456，那么逆序之后就是$A[3,2,1]，B[6,5,4]$
先用3去分别乘6、5、4；再拿2分别乘6、5、4，最后拿1乘。over

#include <iostream>
#include <vector>

using namespace std;

vector<int> mul(const vector<int> &A, const vector<int> &B) {
  vector<int> ret(A.size() + B.size(), 0);

  for (int i = 0; i < A.size(); ++i) {
    int a = A[i];
    for (int j = 0; j < B.size(); ++j) {
      int b = B[j];
      ret[i + j] += a * b;
      ret[i + j + 1] += ret[i + j] / 10;
      ret[i + j] %= 10;
    }
  }
  while (ret.size() > 1 && ret.back() == 0) {
    ret.pop_back();
  }
  return ret;
}

int main() {
  string a = "1332233", b = "1332233";
  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');
  }

  vector<int> ret = mul(A, B);

  for (int i = ret.size() - 1; i >= 0; --i) {
    cout << ret[i];
  }

  return 0;
}

高精度除法

稍等，还在整理…