大整数的运算

1. 学习内容

1.1 介绍

由于编程语言提供的基本数值数据类型表示的数值范围有限，不能满足较大规模的高精度数值计算，因此需要利用其他方法实现高精度数值的计算，于是产生了大数运算。大数运算主要有加、减、乘三种方法。

基本思路：利用数组连续性，将大数每一位上的数字单独取出放入对应的数组格中，然后再对每一位做单独的加减乘运算。形象的说，类似于小学学习加减乘所列的式子。

1.2 参考程序

大整数的比较

#include <cstring>
#include <iostream>

using namespace std;

//将字符数组a的所有位都移到最后，便于对齐计算。
void swap(char a[], int MAX_LEN) {
  int len = strlen(a);
  int shift_right = MAX_LEN - len; //右移位数
  for (int i = len - 1; i >= 0; i--) {
    a[i + shift_right] = a[i];
  }

  for (int i = 0; i < shift_right; i++) {
    a[i] = '0';
  }

  a[MAX_LEN] = 0; //置字符数组结束
}

int main() {
  int MAX_LEN = 100;
  char a[MAX_LEN + 1], b[MAX_LEN + 1];
  char sum[MAX_LEN + 1];
  cin >> a >> b;

  swap(a, MAX_LEN);
  swap(b, MAX_LEN);

  int compare_result = 0; //-1 表示a<b; 1表示a>b；0表示a==b
  for (int i = 0; i < MAX_LEN - 1; i++) {
    if (a[i] > b[i]) {
      compare_result = 1;
      break;
    } else if (a[i] < b[i]) {
      compare_result = -1;
      break;
    }
  }

  cout << compare_result << endl;
}

大整数的加法

#include <cstring>
#include <iostream>

using namespace std;

//将字符数组a的所有位都移到最后，便于对齐计算。
void swap(char a[], int MAX_LEN) {
  int len = strlen(a);
  int shift_right = MAX_LEN - len; //右移位数
  for (int i = len - 1; i >= 0; i--) {
    a[i + shift_right] = a[i];
  }

  for (int i = 0; i < shift_right; i++) {
    a[i] = '0';
  }

  a[MAX_LEN] = 0; //置字符数组结束
}

int main() {
  int MAX_LEN = 100;
  char a[MAX_LEN + 1], b[MAX_LEN + 1];
  char sum[MAX_LEN + 1];
  cin >> a >> b;

  swap(a, MAX_LEN);
  swap(b, MAX_LEN);

  int carry = 0;
  for (int i = MAX_LEN - 1; i >= 0; i--) {
    int digit_sum = (a[i] - '0') + (b[i] - '0') + carry;
    sum[i] = '0' + digit_sum % 10;
    carry = digit_sum / 10;
  }

  //找到第一个非0值
  int start = 0;
  for (int i = 0; i < MAX_LEN; i++) {
    if (sum[i] != '0') {
      start = i;
      break;
    }
  }

  //打印输出
  for (int i = start; i < MAX_LEN; i++) {
    cout << sum[i];
  }
  cout << endl;

  return 0;
}

2. 编程

1. 大整数加法 c005-5: 求两个不超过200位的非负整数的和。
2. 大整数减法 practice-2736：求两个大的正整数相减的差。
3. 大整数乘法 c006-9：求两个不超过200位的非负整数的积。 <!–
4. 大整数的因子 practice-2925：已知正整数k满足2<=k<=9，现给出长度最大为30位的十进制非负整数c，求所有能整除c的k。
5. 大整数除法 practice-2737：求两个大的正整数相除的商。 –>