Casey

高精度（一）

最近更新：2025-02-17 | 字数总计：954 | 阅读估时：4分钟 | 阅读量：次

对于无法直接存储的整型（）可以使用逐位模拟以实现存储与计算。

本文中接下来讨论的的高精度数以及整型均为正数。对于负整数情况，可以通过特殊判断与变换实现。

存储

高精度存储建议采用 vector<int> 容器，相较于一般 int 数组的优势在于长度可动态增长，有效避免数组预开辟空间不足的情况。

高精度数值存储时采用低位在前高位在后的方式，以便于计算，下面是一个高精度数存储的示例。

1	vector<int> nums = {5, 8, 2, 1}; // int n = 1285

对于一个整型变量，可以将其逐位取出，转换为高精度的表示方式，如下。

vector<int> convert(int n) {
  vector<int> res;
  while (n != 0) {
    res.push_back(n % 10);
    n /= 10;
  }
  if (res.size() == 0) {
    res.push_back(0);
  }
  return res;
}

比较

在进行加法及减法前需要对高精度数进行比较，加法的比较用于优化代码、减少判断，减法的比较用于保证结果为正整数。

下面是一个高精度比较 cmp(A, B) 的实现。若 A > B 返回 1 ， A < B 返回 -1 ，相等时则返回 0 。

int cmp(const vector<int> &A, const vector<int> &B) {
  if (A.size() > B.size()) {
    return 1;
  }
  else if (A.size() < B.size()) {
    return -1;
  }
  else {
    for (int i = A.size() - 1; i >= 0; i--) {
      if (A[i] > B[i]) {
        return 1;
      }
      else if (A[i] < B[i]) {
        return -1;
      }
      else {
        continue;
      }
    }
  }
  return 0;
}

加法

两个高精度数 A 和 B （ A >= B ）相加，采用由低位逐位模拟进位加法的方式计算。

vector<int> add(const vector<int> &A, const vector<int> &B) {
  vector<int> res;
  int c = 0; // 进位
  for (int i = 0; i < A.size(); i++) {
    c += A[i];
    if (i < B.size()) {
      c += B[i];
    }
    res.push_back(c % 10);
    c /= 10;
  }
  if (c != 0) res.push_back(c);
  return res;
}

减法

两个高精度数 A 和 B （ A - B ， A >= B ）相减，采用由低位逐位模拟借位减法的方式计算。

vector<int> sub(const vector<int> &A, const vector<int> &B) {
  vector<int> res = 0;
  int c = 0; // 借位
  for (int i = 0; i < A.size(); i++) {
    c = A[i] - c;
    if (i < B.size()) {
      c -= B[i];
    }
    res.push_back((c + 10) % 10);
    if (c < 0) c = 1;
    else c = 0;
  }
  while (res.size() > 1 && res.back() == 0) {
    res.pop_back();
  }
  return res;
}

由于存在有借位减的情况，为了每次减后为了保证结果为正数，需要 (c + 10) % 10 。

乘法

不同于前面逐位模拟的加减法，高精度数 A 乘整型 b ，将整型看做一个整体，逐位将 A[i] 乘 b ，并与当前和相加取模得到当前位的结果。

vector<int> mul(const vector<int> &A, int b) {
  vector<int> res;
  int c = 0;
  for (int i = 0; i < A.size() || c != 0; i++) {
    if (i < A.size()) c += A[i] * b;
    res.push_back(c % 10);
    c /= 10;
  }
  while (res.size() > 1 && res.back() == 0) {
    res.pop_back();
  }
  return res;
}

这里的代码同前面的高精度加减存在有两个不同点，一是乘法的结果长度可能大于高精度数 A 的长度，因此循环时不仅要判断 A.size() 也要判断当前乘积 c 是否为 0 ，二是乘法可能会出现前导 0 ，在输出时需要去除。

除法

高精度数 A 除整型 b ，采用由高位逐位模拟的试除法。

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

由于是从高位开始向后试除，结果需要翻转 reverse() ，同时去除除法中产生的前导 0 。

2025-02-17 该篇文章被 Casey 打上标签: C 算法归为分类: 学习