大数运算之C语言实现

一、 前言

在我们代码编程过程中，我们经常需要处理各种规模的数值。从日常工作中的一些简单算术在到科学研究中的复杂计算，数字无处不在。然而，当数值变的异常庞大时，就需要用到大数运算来进行实现。本文我们将介绍大数运算的基本概念以及C语言实现大数运算的方法。

二、 概念

我们常见的数据其数据范围大都在int(-2^31 ~ 2^31-1)或者long long( -2^62 — 2^62-1)之内，但在一些情况下，我们会遇到超过这个范围的数据，这些数据我们就称之为大数。当然，大数不只是大整数，对于位数较多的小数，如123456799.987654321也适用于大数运算。

大数运算涉及对超出常规数据类型范围的数字进行加减乘除，阶乘，取余等运算。对于大数，我们通常以字符数组的形式存储，因为单个变量无法容纳如此多的位数，其中每个数组元素都对应一个数位。而实现这些运算的大致思路都是模拟竖式计算的过程，即通过模拟进位，借位，取余操作完成计算。

三、 代码实现

下面我们将对大数进行加减乘除，阶乘，取余等运算。

• 大数加法运算

  #include <stdio.h>
  #include <stdlib.h>
  #include <string.h>// 函数声明
  char* reverseString(const char* str);
  char* addLargeNumbers(const char* num1, const char* num2);// 主函数
  int main() {// 输入两个大数char num1[1001]; // 假设大数的最大位数为1000，多加一位用于存储字符串结束符'\0'char num2[1001];printf("请输入第一个大数: ");scanf("%1000s", num1); // 限制输入长度，防止缓冲区溢出printf("请输入第二个大数: ");scanf("%1000s", num2);// 调用大数相加函数char* result = addLargeNumbers(num1, num2);// 输出结果printf("结果: %s\n", result);// 释放动态分配的内存free(result);return 0;
  }// 字符串反转函数
  char* reverseString(const char* str) {int len = strlen(str);char* reversed = (char*)malloc((len + 1) * sizeof(char)); // 分配内存用于存储反转后的字符串for (int i = 0; i < len; i++) {reversed[i] = str[len - 1 - i]; // 反转字符串}reversed[len] = '\0'; // 添加字符串结束符return reversed;
  }// 大数相加函数
  char* addLargeNumbers(const char* num1, const char* num2) {char* reversedNum1 = reverseString(num1); // 反转字符串，便于从低位开始相加char* reversedNum2 = reverseString(num2);int len1 = strlen(reversedNum1);int len2 = strlen(reversedNum2);int maxLen = len1 > len2 ? len1 : len2;int carry = 0; // 进位char* result = (char*)malloc((maxLen + 2) * sizeof(char)); // 分配内存用于存储结果，多加一位用于可能的进位和一位用于字符串结束符// 从低位开始逐位相加for (int i = 0; i < maxLen; i++) {int digit1 = i < len1 ? reversedNum1[i] - '0' : 0;int digit2 = i < len2 ? reversedNum2[i] - '0' : 0;int sum = digit1 + digit2 + carry;carry = sum / 10;result[i] = sum % 10 + '0';}// 处理剩余的进位if (carry) {result[maxLen] = carry + '0';maxLen++;}// 添加字符串结束符result[maxLen] = '\0';// 反转结果字符串，得到正确的顺序char* finalResult = reverseString(result);free(reversedNum1); // 释放反转后的输入字符串内存free(reversedNum2);free(result); // 释放中间结果字符串内存return finalResult; // 返回最终结果字符串
  }
  

  演示：

• 大数减法运算

  #include <stdio.h>
  #include <stdlib.h>
  #include <string.h>
  #include <stdbool.h>// 函数声明
  char* reverseString(const char* str);
  char* subtractLargeNumbers(const char* num1, const char* num2);// 主函数
  int main() {// 输入两个大数char num1[1001]; // 假设大数的最大位数为1000，多加一位用于存储字符串结束符'\0'char num2[1001];printf("请输入被减数: ");scanf("%1000s", num1); // 限制输入长度，防止缓冲区溢出printf("请输入减数: ");scanf("%1000s", num2);// 验证被减数是否大于等于减数（简单比较字符串长度，如果不等则按字典序比较）if (strlen(num1) < strlen(num2) || (strlen(num1) == strlen(num2) && strcmp(num1, num2) < 0)) {printf("错误: 被减数必须大于等于减数。\n");return 1;}// 调用大数相减函数char* result = subtractLargeNumbers(num1, num2);// 输出结果printf("结果: %s\n", result);// 释放动态分配的内存free(result);return 0;
  }// 字符串反转函数（与大数加法中相同）
  char* reverseString(const char* str) {int len = strlen(str);char* reversed = (char*)malloc((len + 1) * sizeof(char));for (int i = 0; i < len; i++) {reversed[i] = str[len - 1 - i];}reversed[len] = '\0';return reversed;
  }// 大数相减函数
  char* subtractLargeNumbers(const char* num1, const char* num2) {char* reversedNum1 = reverseString(num1);char* reversedNum2 = reverseString(num2);int len1 = strlen(reversedNum1);int len2 = strlen(reversedNum2);int maxLen = len1;bool isNegative = false; // 标记结果是否为负数（本实现假设被减数大于等于减数，所以结果不为负数）char* result = (char*)malloc((maxLen + 1) * sizeof(char)); // 分配内存，注意这里不需要额外位用于借位，因为我们已经假设被减数足够大// 从低位开始逐位相减for (int i = 0; i < maxLen; i++) {int digit1 = i < len1 ? reversedNum1[i] - '0' : 0;int digit2 = i < len2 ? reversedNum2[i] - '0' : 0;int diff = digit1 - digit2;// 如果当前位不够减，则从前一位借位if (diff < 0) {diff += 10;// 注意：这里我们不需要修改前一位的值，因为我们是逐位计算并存储结果的// 但是在实际实现中，如果需要保留借位的过程，可以引入一个额外的数组来记录借位情况}result[i] = diff + '0';}// 去除结果前导零int start = 0;while (start < maxLen && result[start] == '0') {start++;}// 如果整个结果都是0，则结果应为"0"if (start == maxLen) {strcpy(result, "0");} else {// 将结果字符串前移，以去除前导零for (int i = 0; i < maxLen - start; i++) {result[i] = result[start + i];}result[maxLen - start] = '\0';}// 反转结果字符串，得到正确的顺序char* finalResult = reverseString(result);free(reversedNum1);free(reversedNum2);free(result); // 注意：这里释放的是去除前导零之前的result内存return finalResult;
  }
  

  演示：
  

• 大数乘法运算

  #include <stdio.h>
  #include <stdlib.h>
  #include <string.h>char* multiplyLargeNumbers(const char* num1, const char* num2);int main() {char num1[1001], num2[1001];printf("请输入第一个大数: ");scanf("%1000s", num1);printf("请输入第二个大数: ");scanf("%1000s", num2);char* result = multiplyLargeNumbers(num1, num2);printf("结果: %s\n", result);free(result - (result[0] == '0' && *(result + 1) == '\0')); // Adjust free pointer if leading '0' was logically removedreturn 0;
  }char* multiplyLargeNumbers(const char* num1, const char* num2) {int len1 = strlen(num1);int len2 = strlen(num2);int maxLen = len1 + len2;char* result = (char*)calloc(maxLen + 1, sizeof(char)); // +1 for null terminator// Initialize result array with zerosmemset(result, '0', maxLen);result[maxLen] = '\0';// Perform multiplicationfor (int i = len1 - 1; i >= 0; i--) {for (int j = len2 - 1, k = i + j; j >= 0; j--, k--) {int mul = (num1[i] - '0') * (num2[j] - '0');int sum = mul + (result[k + 1] - '0');result[k + 1] = (sum % 10) + '0';result[k] += sum / 10;if (result[k] > '9') {int carry = result[k] - '0' / 10;result[k] = (result[k] - carry * 10) + '0';if (k > 0) {result[k - 1] += carry;} else {// Handle carry overflow, resize result if necessarychar* temp = (char*)realloc(result, maxLen + 2);if (temp) {result = temp;memmove(result + 1, result, maxLen + 1);result[0] = '0' + carry;maxLen++;} else {// Allocation failed, handle errorfree(result);return NULL;}}}}}// Find the start of the non-zero part of the resultint start = 0;while (start < maxLen && result[start] == '0') {start++;}// Shift the result to the left and null-terminate itmemmove(result, result + start, maxLen - start + 1);return result;
  }

  演示：
  

• 大数除法及取余运算

  #include <stdio.h>
  #include <string.h>void divideLargeNumber(int *largeNumberArray, int divisionFactor, int numberOfDigits);int main()
  {char largeNumberStr[1000]; // 存储大整数的字符串int divisor; // 除数printf("请输入一个大整数（不超过999位）和一个除数（以空格分隔）：");scanf("%s%d", largeNumberStr, &divisor);int largeNumberDigits[1000]; // 存储大整数的每一位数字int numberLength = strlen(largeNumberStr); // 大整数的长度for (int i = 0; i < numberLength; i++)largeNumberDigits[i] = largeNumberStr[i] - '0';divideLargeNumber(largeNumberDigits, divisor, numberLength);return 0;
  }void divideLargeNumber(int *largeNumberArray, int divisionFactor, int numberOfDigits) // 开始操作
  {int partialSum = 0; // 当前部分和（累加当前位及之前的数字）int firstDigitOutputFlag = 0; // 标记是否已输出第一个非零商位int remainder = 0; // 余数for (int i = 0; i < numberOfDigits; i++) // 这里没有将商存下来，而是找到一位就输出{partialSum += largeNumberArray[i];if (partialSum < divisionFactor && firstDigitOutputFlag){remainder = partialSum; // 记录有可能最后加上最后一位还是小于divisionFactor的情况的余数printf("0"); // 输出商位为0的情况}if (partialSum >= divisionFactor){printf("商位: %d", partialSum / divisionFactor);partialSum %= divisionFactor; // 更新余数remainder = partialSum; // 记录最后加上最后一位大于divisionFactor的情况的余数partialSum *= 10; // 为下一位数字做准备firstDigitOutputFlag = 1; // 在找到第一个商位之后改变标记状态}else{partialSum *= 10; // 如果当前部分和小于除数，则继续累加下一位数字}}printf("\n");printf("余数：%d\n", remainder); // 输出余数
  }
  

  演示：
  

• 大数阶乘运算

  #include <stdio.h>
  #include <string.h>
  #include <stdbool.h>#define MAX_DIGITS 1000 // 假设最大阶乘位数不超过1000// 辅助函数：打印大数
  void printLargeNumber(int result[], int length) {for (int i = length - 1; i >= 0; i--) {printf("%d", result[i]);}printf("\n");
  }// 大数阶乘函数
  void factorialLargeNumber(int n, int result[], int* length) {// 初始化结果数组为1（阶乘的初始值）memset(result, 0, sizeof(int) * MAX_DIGITS);result[0] = 1;*length = 1;// 计算阶乘for (int i = 2; i <= n; i++) {int carry = 0; // 进位for (int j = 0; j < *length; j++) {int product = result[j] * i + carry;result[j] = product % 10; // 当前位的值carry = product / 10;     // 进位}// 处理进位while (carry) {result[*length] = carry % 10;carry = carry / 10;(*length)++;}}
  }int main() {int n;printf("请输入一个整数: ");scanf("%d", &n);int result[MAX_DIGITS];int length = 0;factorialLargeNumber(n, result, &length);printf("%d! = ", n);printLargeNumber(result, length);return 0;
  }
  

  演示：
  

四、小结

好了，关于大数运算的代码实现到我们这里就结束了，后面遇到其它我会在继续接着补充，希望对大家有所帮助。