搜索
C语言

C语言大整数四则运算如何高效实现？

99ANYc3cd6
99ANYc3cd6 / / 0 评论 / 9 阅读
作者有点忙，还没来得及写简介......
预计阅读时长 29 分钟
位置： 首页 › C语言 › 正文

C语言大整数的四则运算

在C语言中，基本数据类型（如int、long等）能够表示的整数范围有限，当需要处理超过这些类型范围的整数时，就需要实现大整数运算，下面我将介绍如何使用C语言实现大整数的加、减、乘、除四则运算。

c语言大整数的四则运算
（图片来源网络，侵删）

数据结构设计

我们需要定义一个数据结构来存储大整数，通常使用数组来存储每一位数字,并用一个变量记录整数的符号和长度。

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>
#define MAX_DIGITS 1000  // 最大位数
typedef struct {
    bool sign;          // 符号，true为负，false为正
    int digits[MAX_DIGITS]; // 数字数组，digits[0]为最低位
    int length;         // 实际位数
} BigInt;

辅助函数

1 初始化函数

void initBigInt(BigInt *num, bool sign, const char *str) {
    num->sign = sign;
    num->length = 0;
    int len = strlen(str);
    for (int i = 0; i < len; i++) {
        if (i == 0 && str[i] == '-') {
            num->sign = true;
            continue;
        }
        num->digits[num->length++] = str[i] - '0';
    }
    // 去除前导零
    while (num->length > 1 && num->digits[num->length - 1] == 0) {
        num->length--;
    }
}

2 打印函数

void printBigInt(const BigInt *num) {
    if (num->sign) {
        printf("-");
    }
    for (int i = num->length - 1; i >= 0; i--) {
        printf("%d", num->digits[i]);
    }
    printf("\n");
}

3 比较函数

int compareBigInt(const BigInt *a, const BigInt *b) {
    if (a->length != b->length) {
        return a->length - b->length;
    }
    for (int i = a->length - 1; i >= 0; i--) {
        if (a->digits[i] != b->digits[i]) {
            return a->digits[i] - b->digits[i];
        }
    }
    return 0;
}

四则运算实现

1 加法

void addBigInt(const BigInt *a, const BigInt *b, BigInt *result) {
    bool sign = false; // 默认结果为正
    // 处理符号
    if (a->sign && !b->sign) {
        BigInt temp = *b;
        temp.sign = true;
        subtractBigInt(a, &temp, result);
        return;
    } else if (!a->sign && b->sign) {
        BigInt temp = *a;
        temp.sign = true;
        subtractBigInt(b, &temp, result);
        return;
    } else {
        sign = a->sign; // 同号，结果符号与a相同
    }
    int carry = 0;
    int max_len = (a->length > b->length) ? a->length : b->length;
    result->length = 0;
    for (int i = 0; i < max_len || carry; i++) {
        int digit_a = (i < a->length) ? a->digits[i] : 0;
        int digit_b = (i < b->length) ? b->digits[i] : 0;
        int sum = digit_a + digit_b + carry;
        result->digits[result->length++] = sum % 10;
        carry = sum / 10;
    }
    result->sign = sign;
}

2 减法

void subtractBigInt(const BigInt *a, const BigInt *b, BigInt *result) {
    bool sign = false; // 默认结果为正
    // 处理符号
    if (a->sign && !b->sign) {
        BigInt temp = *b;
        temp.sign = true;
        addBigInt(a, &temp, result);
        return;
    } else if (!a->sign && b->sign) {
        BigInt temp = *a;
        temp.sign = true;
        addBigInt(b, &temp, result);
        return;
    } else if (a->sign && b->sign) {
        // 同号，比较绝对值大小
        int cmp = compareBigInt(a, b);
        if (cmp < 0) {
            subtractBigInt(b, a, result);
            result->sign = true;
        } else {
            subtractBigInt(a, b, result);
        }
        return;
    }
    // 异号或同号且a的绝对值大于等于b
    int cmp = compareBigInt(a, b);
    if (cmp < 0) {
        subtractBigInt(b, a, result);
        result->sign = true;
        return;
    }
    int borrow = 0;
    result->length = 0;
    for (int i = 0; i < a->length; i++) {
        int digit_a = a->digits[i];
        int digit_b = (i < b->length) ? b->digits[i] : 0;
        digit_a -= borrow;
        borrow = 0;
        if (digit_a < digit_b) {
            digit_a += 10;
            borrow = 1;
        }
        result->digits[result->length++] = digit_a - digit_b;
    }
    // 去除前导零
    while (result->length > 1 && result->digits[result->length - 1] == 0) {
        result->length--;
    }
}

3 乘法

void multiplyBigInt(const BigInt *a, const BigInt *b, BigInt *result) {
    bool sign = a->sign ^ b->sign; // 结果符号为a和b符号的异或
    // 初始化结果为0
    result->length = 0;
    memset(result->digits, 0, sizeof(result->digits));
    for (int i = 0; i < a->length; i++) {
        int carry = 0;
        for (int j = 0; j < b->length || carry; j++) {
            int digit_b = (j < b->length) ? b->digits[j] : 0;
            int product = a->digits[i] * digit_b + carry + result->digits[i + j];
            result->digits[i + j] = product % 10;
            carry = product / 10;
        }
    }
    result->length = a->length + b->length;
    // 去除前导零
    while (result->length > 1 && result->digits[result->length - 1] == 0) {
        result->length--;
    }
    result->sign = sign;
}

4 除法

void divideBigInt(const BigInt *a, const BigInt *b, BigInt *result) {
    bool sign = a->sign ^ b->sign; // 结果符号为a和b符号的异或
    // 处理除数为0的情况
    if (b->length == 1 && b->digits[0] == 0) {
        printf("Error: Division by zero\n");
        exit(1);
    }
    // 初始化结果为0
    result->length = 0;
    memset(result->digits, 0, sizeof(result->digits));
    BigInt remainder;
    remainder.length = 0;
    memset(remainder.digits, 0, sizeof(remainder.digits));
    for (int i = a->length - 1; i >= 0; i--) {
        // 将余数左移一位
        for (int j = remainder.length; j > 0; j--) {
            remainder.digits[j] = remainder.digits[j - 1];
        }
        remainder.digits[0] = a->digits[i];
        remainder.length++;
        // 去除余数的前导零
        while (remainder.length > 1 && remainder.digits[remainder.length - 1] == 0) {
            remainder.length--;
        }
        // 计算当前位的商
        int quotient = 0;
        while (compareBigInt(&remainder, b) >= 0) {
            subtractBigInt(&remainder, b, &remainder);
            quotient++;
        }
        result->digits[result->length++] = quotient;
    }
    // 反转结果数组
    for (int i = 0; i < result->length / 2; i++) {
        int temp = result->digits[i];
        result->digits[i] = result->digits[result->length - 1 - i];
        result->digits[result->length - 1 - i] = temp;
    }
    // 去除前导零
    while (result->length > 1 && result->digits[result->length - 1] == 0) {
        result->length--;
    }
    result->sign = sign;
}

使用示例

int main() {
    BigInt a, b, result;
    // 初始化大整数
    initBigInt(&a, false, "12345678901234567890");
    initBigInt(&b, false, "98765432109876543210");
    printf("a = ");
    printBigInt(&a);
    printf("b = ");
    printBigInt(&b);
    // 加法
    addBigInt(&a, &b, &result);
    printf("a + b = ");
    printBigInt(&result);
    // 减法
    subtractBigInt(&a, &b, &result);
    printf("a - b = ");
    printBigInt(&result);
    // 乘法
    multiplyBigInt(&a, &b, &result);
    printf("a * b = ");
    printBigInt(&result);
    // 除法
    divideBigInt(&a, &b, &result);
    printf("a / b = ");
    printBigInt(&result);
    return 0;
}

优化建议

  1. 动态内存分配：当前实现使用固定大小的数组,可以改为动态分配内存以适应任意大小的整数。

  2. 更高效的算法：

    • 乘法可以使用Karatsuba算法或FFT加速
    • 除法可以使用牛顿迭代法等优化算法

  3. 输入输出优化：可以添加从字符串直接构造大整数的方法,以及格式化输出的方法。

    c语言大整数的四则运算
    （图片来源网络，侵删）

  4. 错误处理：添加更完善的错误处理机制，如除零检查、非法字符检查等。

  5. 运算符重载：如果使用C++,可以重载运算符使代码更直观。

这个实现提供了大整数四则运算的基本框架,可以根据具体需求进行扩展和优化。

c语言大整数的四则运算
（图片来源网络，侵删）
-- 展开阅读全文 --
头像
C语言如何将百分制成绩转换为等级？
« 上一篇 04-30
dede搜索模板制作步骤是怎样的？
下一篇 » 04-30

相关文章

取消
微信二维码
支付宝二维码

目录[+]