当前位置： 首页 > article >正文

大数运算之C语言实现

article 2025/1/27 7:29:17

一、 前言

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

    return 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 zeros
    memset(result, '0', maxLen);
    result[maxLen] = '\0';

    // Perform multiplication
    for (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 necessary
                    char* 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 error
                        free(result);
                        return NULL;
                    }
                }
            }
        }
    }

    // Find the start of the non-zero part of the result
    int start = 0;
    while (start < maxLen && result[start] == '0') {
        start++;
    }

    // Shift the result to the left and null-terminate it
    memmove(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;
}

    演示：
    在这里插入图片描述

四、小结

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


http://www.kler.cn/a/518751.html

相关文章：

  • 2025_1_26 c++中关于构造和析构的顺序
  • HTB：Support[WriteUP]
  • Spring Data JPA 实战：构建高性能数据访问层
  • 为AI聊天工具添加一个知识系统 之69 详细设计 之10 三种中台和时间度量 之2
  • 2024年AI多极竞争：技术创新与商业突破
  • hedfs和hive数据迁移后校验脚本
  • STM32项目分享：智能语音分类垃圾桶
  • 基于Flask的微博话题舆情分析可视化系统的设计与实现
  • Java Swing 基础组件详解 [论文投稿-第四届智能系统、通信与计算机网络]
  • 数据结构与算法之堆: LeetCode 208. 实现 Trie (前缀树) (Ts版)
  • Java面试题2025-Mysql
  • Pandas与Numpy的数据分析进阶题
  • 免费GPU算力，不花钱部署DeepSeek-R1
  • 【由浅入深认识Maven】第2部分 maven依赖管理与仓库机制
  • 基于大语言模型构建本地个人AI助理
  • WebRtc06: 音视频数据采集
  • ICSE‘25 LLM Assistance for Memory Safety
  • 【面试】【程序员基本知识】计算机网络，设计模式，正则，安全
  • 一文简单回顾复习Java基础概念
  • InfiniBand客户端注册机制详解：ib_register_client函数的作用与实现
  • DDD架构实战第六讲总结：领域驱动设计中的聚合
  • 近年流行的开发技术
  • 02-AD-绘制原理图(画示意图+添加已有P封装)
  • MySQL核心知识：春招面试数据库要点
  • PyQt6医疗多模态大语言模型（MLLM）实用系统框架构建初探（上.文章部分）
  • 使用 Serilog 在 .NET Core 6.0 中日志记录