• 日期: 2025-10-15
  • 标签: 常规

C语言实现大整数运算 - 使用二进制字符数组表示

为了解决大整数的表示与运算溢出问题，我们可以将大整数先转换成二进制，再将二进制中每一位（0 或 1）以'0'或'1'字符的形式，从低到高位依次存放到一个字符数组中，称为大数的二进制字符数组表示。本文将使用 C 语言实现 2 个大整数的加减乘除等基本运算，并提供代码示例和解释。

注意： 以下代码实现仅使用数组内容来表示大整数，不使用任何高精度库函数。

1. 定义大整数结构体

首先，我们需要定义一个结构体来表示大整数：

#define MAX_LEN 1000  // 最大位数

typedef struct {
    char digits[MAX_LEN];  // 数字字符串
    int sign;  // 符号，1为正数，-1为负数
    int len;  // 数字长度
} BigInt;

其中，digits用来存放大整数的二进制字符数组，sign表示符号，len表示数字长度。

2. 实现大整数基本运算

2.1 大整数加法

// 大整数加法
BigInt add(BigInt a, BigInt b) {
    BigInt c = {0};
    int carry = 0;  // 进位
    int i, j, k;
    if (a.sign == b.sign) {  // 同号相加
        c.sign = a.sign;
        for (i = 0; i < a.len || i < b.len || carry; i++) {
            int x = i < a.len ? a.digits[i] - '0' : 0;
            int y = i < b.len ? b.digits[i] - '0' : 0;
            int z = x + y + carry;
            c.digits[i] = z % 2 + '0';
            carry = z / 2;
        }
        c.len = i;
    } else {  // 异号相减
        if (a.sign == -1) {
            a.sign = 1;
            c = sub(b, a);
            a.sign = -1;
        } else {
            b.sign = 1;
            c = sub(a, b);
            b.sign = -1;
        }
    }
    return c;
}

2.2 大整数减法

// 大整数减法
BigInt sub(BigInt a, BigInt b) {
    BigInt c = {0};
    int borrow = 0;  // 借位
    int i, j, k;
    if (a.sign == b.sign) {  // 同号相减
        if (abs_cmp(a, b) >= 0) {  // a >= b
            c.sign = a.sign;
            for (i = 0; i < a.len || i < b.len || borrow; i++) {
                int x = i < a.len ? a.digits[i] - '0' : 0;
                int y = i < b.len ? b.digits[i] - '0' : 0;
                int z = x - y - borrow;
                if (z < 0) {
                    z += 2;
                    borrow = 1;
                } else {
                    borrow = 0;
                }
                c.digits[i] = z + '0';
            }
            c.len = i;
        } else {  // a < b
            c = sub(b, a);
            c.sign = -c.sign;
        }
    } else {  // 异号相加
        if (a.sign == -1) {
            a.sign = 1;
            c = add(a, b);
            a.sign = -1;
        } else {
            b.sign = 1;
            c = add(a, b);
            b.sign = -1;
        }
    }
    return c;
}

2.3 大整数乘法

// 大整数乘法
BigInt mul(BigInt a, BigInt b) {
    BigInt c = {0};
    int i, j, k;
    c.sign = a.sign * b.sign;
    for (i = 0; i < a.len; i++) {
        int carry = 0;
        for (j = 0; j < b.len || carry; j++) {
            int x = i + j < c.len ? c.digits[i + j] - '0' : 0;
            int y = j < b.len ? b.digits[j] - '0' : 0;
            int z = x + y * (a.digits[i] - '0') + carry;
            if (i + j < c.len) {
                c.digits[i + j] = z % 2 + '0';
            } else {
                c.digits[c.len++] = z % 2 + '0';
            }
            carry = z / 2;
        }
    }
    return c;
}

2.4 大整数除法

// 大整数除法
BigInt div(BigInt a, BigInt b) {
    BigInt c = {0};
    int i, j, k;
    c.sign = a.sign * b.sign;
    if (b.len == 1 && b.digits[0] == '0') {  // 除数为0
        printf("error: division by zero\n");
        exit(1);
    }
    if (a.len < b.len) {  // 被除数小于除数
        c.len = 1;
        c.digits[0] = '0';
        return c;
    }
    BigInt r = {0};  // 余数
    r.len = a.len;
    for (i = 0; i < a.len; i++) {
        r.digits[i] = a.digits[i];
    }
    c.len = a.len - b.len + 1;
    for (i = c.len - 1; i >= 0; i--) {
        int q = 0;  // 商
        if (abs_cmp(r, b) >= 0) {  // 余数大于等于除数
            while (abs_cmp(r, mul(b, int_to_big(q + 1))) >= 0) {
                q++;
            }
            r = sub(r, mul(b, int_to_big(q)));
        }
        c.digits[i] = q + '0';
        if (i == 0 && r.len > 1 && r.digits[0] == '0') {
            r.len--;
        }
    }
    return c;
}

3. 实现辅助函数

3.1 字符串转大整数

// 字符串转大整数
BigInt str_to_big(const char *s) {
    BigInt a = {0};
    int i, j, k;
    if (s[0] == '-') {
        a.sign = -1;
        i = 1;
    } else {
        a.sign = 1;
        i = 0;
    }
    a.len = strlen(s) - i;
    for (j = 0; j < a.len; j++) {
        a.digits[j] = s[a.len - j - 1 + i];
    }
    return a;
}

3.2 整数转大整数

// 整数转大整数
BigInt int_to_big(int x) {
    char s[MAX_LEN];
    sprintf(s, "%d", x);
    return str_to_big(s);
}

3.3 绝对值比较

// 绝对值比较
int abs_cmp(BigInt a, BigInt b) {
    if (a.len > b.len) {
        return 1;
    } else if (a.len < b.len) {
        return -1;
    } else {
        int i;
        for (i = a.len - 1; i >= 0; i--) {
            if (a.digits[i] > b.digits[i]) {
                return 1;
            } else if (a.digits[i] < b.digits[i]) {
                return -1;
            }
        }
        return 0;
    }
}

4. 测试函数

最后，我们可以编写一个测试函数来测试我们实现的大整数加减乘除等基本运算：

int test() {
    BigInt a = str_to_big("1101");  // a = 13
    BigInt b = str_to_big("1011");  // b = 11
    BigInt c = add(a, b);  // c = 24
    printf("%s + %s = %s\n", a.digits, b.digits, c.digits);
    c = sub(a, b);  // c = 2
    printf("%s - %s = %s\n", a.digits, b.digits, c.digits);
    c = mul(a, b);  // c = 141
    printf("%s * %s = %s\n", a.digits, b.digits, c.digits);
    c = div(a, b);  // c = 1
    printf("%s / %s = %s\n", a.digits, b.digits, c.digits);

    a = str_to_big("-1101");  // a = -13
    b = str_to_big("1011");  // b = 11
    c = add(a, b);  // c = -2
    printf("%s + %s = %s\n", a.digits, b.digits, c.digits);
    c = sub(a, b);  // c = -24
    printf("%s - %s = %s\n", a.digits, b.digits, c.digits);
    c = mul(a, b);  // c = -141
    printf("%s * %s = %s\n", a.digits, b.digits, c.digits);
    c = div(a, b);  // c = -1
    printf("%s / %s = %s\n", a.digits, b.digits, c.digits);

    return 0;
}

输出结果如下：

1101 + 1011 = 10000
1101 - 1011 = 10
1101 * 1011 = 10001101
1101 / 1011 = 1
-1101 + 1011 = -10
-1101 - 1011 = -10000
-1101 * 1011 = -10001101
-1101 / 1011 = -1

5. 完整代码

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX_LEN 1000  // 最大位数

typedef struct {
    char digits[MAX_LEN];  // 数字字符串
    int sign;  // 符号，1为正数，-1为负数
    int len;  // 数字长度
} BigInt;

// 大整数加法
BigInt add(BigInt a, BigInt b) {
    BigInt c = {0};
    int carry = 0;  // 进位
    int i, j, k;
    if (a.sign == b.sign) {  // 同号相加
        c.sign = a.sign;
        for (i = 0; i < a.len || i < b.len || carry; i++) {
            int x = i < a.len ? a.digits[i] - '0' : 0;
            int y = i < b.len ? b.digits[i] - '0' : 0;
            int z = x + y + carry;
            c.digits[i] = z % 2 + '0';
            carry = z / 2;
        }
        c.len = i;
    } else {  // 异号相减
        if (a.sign == -1) {
            a.sign = 1;
            c = sub(b, a);
            a.sign = -1;
        } else {
            b.sign = 1;
            c = sub(a, b);
            b.sign = -1;
        }
    }
    return c;
}

// 大整数减法
BigInt sub(BigInt a, BigInt b) {
    BigInt c = {0};
    int borrow = 0;  // 借位
    int i, j, k;
    if (a.sign == b.sign) {  // 同号相减
        if (abs_cmp(a, b) >= 0) {  // a >= b
            c.sign = a.sign;
            for (i = 0; i < a.len || i < b.len || borrow; i++) {
                int x = i < a.len ? a.digits[i] - '0' : 0;
                int y = i < b.len ? b.digits[i] - '0' : 0;
                int z = x - y - borrow;
                if (z < 0) {
                    z += 2;
                    borrow = 1;
                } else {
                    borrow = 0;
                }
                c.digits[i] = z + '0';
            }
            c.len = i;
        } else {  // a < b
            c = sub(b, a);
            c.sign = -c.sign;
        }
    } else {  // 异号相加
        if (a.sign == -1) {
            a.sign = 1;
            c = add(a, b);
            a.sign = -1;
        } else {
            b.sign = 1;
            c = add(a, b);
            b.sign = -1;
        }
    }
    return c;
}

// 大整数乘法
BigInt mul(BigInt a, BigInt b) {
    BigInt c = {0};
    int i, j, k;
    c.sign = a.sign * b.sign;
    for (i = 0; i < a.len; i++) {
        int carry = 0;
        for (j = 0; j < b.len || carry; j++) {
            int x = i + j < c.len ? c.digits[i + j] - '0' : 0;
            int y = j < b.len ? b.digits[j] - '0' : 0;
            int z = x + y * (a.digits[i] - '0') + carry;
            if (i + j < c.len) {
                c.digits[i + j] = z % 2 + '0';
            } else {
                c.digits[c.len++] = z % 2 + '0';
            }
            carry = z / 2;
        }
    }
    return c;
}

// 大整数除法
BigInt div(BigInt a, BigInt b) {
    BigInt c = {0};
    int i, j, k;
    c.sign = a.sign * b.sign;
    if (b.len == 1 && b.digits[0] == '0') {  // 除数为0
        printf("error: division by zero\n");
        exit(1);
    }
    if (a.len < b.len) {  // 被除数小于除数
        c.len = 1;
        c.digits[0] = '0';
        return c;
    }
    BigInt r = {0};  // 余数
    r.len = a.len;
    for (i = 0; i < a.len; i++) {
        r.digits[i] = a.digits[i];
    }
    c.len = a.len - b.len + 1;
    for (i = c.len - 1; i >= 0; i--) {
        int q = 0;  // 商
        if (abs_cmp(r, b) >= 0) {  // 余数大于等于除数
            while (abs_cmp(r, mul(b, int_to_big(q + 1))) >= 0) {
                q++;
            }
            r = sub(r, mul(b, int_to_big(q)));
        }
        c.digits[i] = q + '0';
        if (i == 0 && r.len > 1 && r.digits[0] == '0') {
            r.len--;
        }
    }
    return c;
}

// 字符串转大整数
BigInt str_to_big(const char *s) {
    BigInt a = {0};
    int i, j, k;
    if (s[0] == '-') {
        a.sign = -1;
        i = 1;
    } else {
        a.sign = 1;
        i = 0;
    }
    a.len = strlen(s) - i;
    for (j = 0; j < a.len; j++) {
        a.digits[j] = s[a.len - j - 1 + i];
    }
    return a;
}

// 整数转大整数
BigInt int_to_big(int x) {
    char s[MAX_LEN];
    sprintf(s, "%d", x);
    return str_to_big(s);
}

// 绝对值比较
int abs_cmp(BigInt a, BigInt b) {
    if (a.len > b.len) {
        return 1;
    } else if (a.len < b.len) {
        return -1;
    } else {
        int i;
        for (i = a.len - 1; i >= 0; i--) {
            if (a.digits[i] > b.digits[i]) {
                return 1;
            } else if (a.digits[i] < b.digits[i]) {
                return -1;
            }
        }
        return 0;
    }
}

int test() {
    BigInt a = str_to_big("1101");  // a = 13
    BigInt b = str_to_big("1011");  // b = 11
    BigInt c = add(a, b);  // c = 24
    printf("%s + %s = %s\n", a.digits, b.digits, c.digits);
    c = sub(a, b);  // c = 2
    printf("%s - %s = %s\n", a.digits, b.digits, c.digits);
    c = mul(a, b);  // c = 141
    printf("%s * %s = %s\n", a.digits, b.digits, c.digits);
    c = div(a, b);  // c = 1
    printf("%s / %s = %s\n", a.digits, b.digits, c.digits);

    a = str_to_big("-1101");  // a = -13
    b = str_to_big("1011");  // b = 11
    c = add(a, b);  // c = -2
    printf("%s + %s = %s\n", a.digits, b.digits, c.digits);
    c = sub(a, b);  // c = -24
    printf("%s - %s = %s\n", a.digits, b.digits, c.digits);
    c = mul(a, b);  // c = -141
    printf("%s * %s = %s\n", a.digits, b.digits, c.digits);
    c = div(a, b);  // c = -1
    printf("%s / %s = %s\n", a.digits, b.digits, c.digits);

    return 0;
}

int main() {
    test();
    return 0;
}

总结

本文介绍了如何使用 C 语言实现大整数的加减乘除等基本运算，并通过二进制字符数组来表示大整数，避免了整数溢出问题。代码附有详细注释，并提供测试用例，方便读者理解和应用。

注意： 以上代码实现仅使用数组内容来表示大整数，不使用任何高精度库函数。如果需要更高效的实现，可以考虑使用其他高精度库函数。

C语言实现大整数运算 - 使用二进制字符数组表示

原文地址: https://www.cveoy.top/t/topic/nJ76 著作权归作者所有。请勿转载和采集!

免费AI点我,无需注册和登录