使用C++实现大整数的四则、模幂运算 |21xrx.com

使用C++实现大整数的四则、模幂运算

2023-07-02 17:04:25 深夜i 27 0

C++ 大整数四则运算模幂运算

C++ 是一种十分强大的编程语言，其支持大整数运算。对于很多需要处理大整数场景的开发者而言，C++ 的这个特性则是十分实用和重要的。今天，本文将向读者介绍如何使用C++来实现大整数的四则运算与模幂运算。

首先，我们需要了解一个C++中的重要数据类型：`string` 类型。该数据类型不仅可以表示字符串，还可以存储大整数。我们可以使用 `string` 类型来表示我们需要进行大整数运算的数字。

四则运算是大整数运算中最基本的部分。我们可以使用 `string` 类型来存储大整数并实现四则运算。下面是一个用 C++ 实现的加法函数：

string add(string a, string b) {
  int lena = a.length();
  int lenb = b.length();
  int len = max(lena, lenb);
  int carry = 0;
  string res;
  for(int i = 0; i < len; i++) {
    if(i < lena) carry += a[lena - i - 1] - '0';
    if(i < lenb) carry += b[lenb - i - 1] - '0';
    res += (carry % 10) + '0';
    carry /= 10;
  }
  if(carry) res += carry + '0';
  reverse(res.begin(), res.end());
  return res;
}

该函数利用循环结构和模运算实现了两个大整数的加法。我们只需要将两个大整数转换为 `string` 类型，便可以直接调用该函数实现大整数之间的加法运算。

与加法类似，我们也可以实现减法、乘法、除法等其他运算。在使用 `string` 类型进行乘法运算时，需要用一个数组来存储进位结果。以下是乘法的一个实现：

string multiply(string a, string b) {
  int lena = a.length();
  int lenb = b.length();
  vector<int> result(lena + lenb, 0);
  for(int i = 0; i < lena; i++) {
    for(int j = 0; j < lenb; j++) {
      result[i + j] += (a[lena - i - 1] - '0') * (b[lenb - j - 1] - '0');
      result[i + j + 1] += result[i + j] / 10;
      result[i + j] %= 10;
    }
  }
  int len = lena + lenb;
  while(len > 1 && result[len - 1] == 0) len--;
  string res(len, '0');
  for(int i = 0; i < len; i++) res[len - i - 1] = result[i] + '0';
  return res;
}

对于模幂运算，我们可以使用递归来实现快速幂。以下是模幂运算的一个实现：

string mod_pow(string x, int n, string mod) {
  if(n == 0) return "1";
  string res = mod_pow(x, n / 2, mod);
  res = multiply(res, res);
  if(n % 2 == 1) res = multiply(res, x);
  return mod(res, mod);
}

该函数使用递归实现快速幂，同时使用上述实现的乘法函数 `multiply` 和模运算函数 `mod`。

C++中实现大整数的四则运算与模幂运算无需引用第三方库，只需使用 `string` 类型和基本库函数，即可快速实现。有了这些工具，处理大整数的场景便能更加方便和高效！

上一篇: idea打包java可执行jar包

下一篇: C++结构体和类的区别

评论区

相似文章