C语言实现大整数运算：二进制字符数组表示法

为了解决大整数表示和运算过程中可能出现的溢出问题，我们可以使用二进制字符数组表示法来存储和处理大整数。这种方法将大整数转换为二进制形式，并将其每一位（0或1）以'0'或'1'字符的形式从低到高位依次存放到一个字符数组中。本文将使用 C 语言实现该方法，并提供加减乘除等基本运算的代码示例。

代码实现

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

#define MAX_LEN 1000 // 定义最大位数

// 将大整数转换成二进制字符数组表示
void intToBinary(int num, char binary[]) {
    int i = 0;
    if (num < 0) {
        binary[i++] = '-'; // 如果是负数，先在数组中添加一个负号字符
        num = -num; // 将负数转换成正数
    }
    int j = i;
    while (num > 0) {
        binary[j++] = num % 2 + '0'; // 取出二进制位，转换成字符形式存放到数组中
        num /= 2;
    }
    binary[j] = '\0'; // 最后加上字符串结束符
    // 将数组中的字符反转，使其从低到高位依次存放
    for (int k = i; k < j / 2; k++) {
        char temp = binary[k];
        binary[k] = binary[j - k - 1];
        binary[j - k - 1] = temp;
    }
}

// 将二进制字符数组表示的大整数转换成整型
int binaryToInt(char binary[]) {
    int i = 0, num = 0;
    int sign = 1; // 符号，正数为1，负数为-1
    if (binary[i] == '-') {
        sign = -1;
        i++;
    }
    while (binary[i] != '\0') {
        num = num * 2 + (binary[i] - '0'); // 依次取出每一位，将字符转换成数字
        i++;
    }
    return num * sign; // 返回最终结果
}

// 获取大整数的符号
int getSign(char num[]) {
    if (num[0] == '-') {
        return -1;
    } else {
        return 1;
    }
}

// 去除大整数前面的0
void removeLeadingZeros(char num[]) {
    int i = 0;
    while (num[i] == '0' && num[i + 1] != '\0') {
        i++;
    }
    if (i > 0) {
        memmove(num, num + i, strlen(num + i) + 1); // 移动字符数组
    }
}

// 大整数加法
void add(char num1[], char num2[], char result[]) {
    int sign1 = getSign(num1);
    int sign2 = getSign(num2);
    if (sign1 * sign2 == 1) { // 如果两个数的符号相同
        // 将两个数转换成整型，相加后再转换成二进制字符数组
        int sum = binaryToInt(num1) + binaryToInt(num2);
        intToBinary(sum, result);
    } else { // 如果两个数的符号不同
        // 将两个数的符号取反，然后做减法
        if (sign1 == -1) {
            num1++; // 跳过负号字符
        }
        if (sign2 == -1) {
            num2++; // 跳过负号字符
        }
        subtract(num1, num2, result);
        if (sign1 == -1) {
            num1--; // 恢复负号字符
        }
        if (sign2 == -1) {
            num2--; // 恢复负号字符
        }
    }
}

// 大整数减法
void subtract(char num1[], char num2[], char result[]) {
    int sign1 = getSign(num1);
    int sign2 = getSign(num2);
    if (sign2 == -1) { // 如果被减数为负数，先将其符号取反，再做加法
        num2++; // 跳过负号字符
        add(num1, num2, result);
        num2--; // 恢复负号字符
    } else if (sign1 == -1) { // 如果减数为负数，先将其符号取反，再做加法
        num1++; // 跳过负号字符
        add(num1, num2, result);
        result[0] = '-'; // 结果为负数
        num1--; // 恢复负号字符
    } else { // 如果两个数的符号相同
        // 将两个数转换成整型，相减后再转换成二进制字符数组
        int diff = binaryToInt(num1) - binaryToInt(num2);
        intToBinary(diff, result);
    }
}

// 大整数乘法
void multiply(char num1[], char num2[], char result[]) {
    int sign1 = getSign(num1);
    int sign2 = getSign(num2);
    // 将两个数转换成整型，相乘后再转换成二进制字符数组
    int product = binaryToInt(num1) * binaryToInt(num2);
    intToBinary(product, result);
    if (sign1 * sign2 == -1) { // 如果两个数的符号不同
        // 结果为负数
        memmove(result + 1, result, strlen(result) + 1); // 移动字符数组
        result[0] = '-';
    }
}

// 大整数除法
void divide(char num1[], char num2[], char result[]) {
    int sign1 = getSign(num1);
    int sign2 = getSign(num2);
    // 将两个数转换成整型，相除后再转换成二进制字符数组
    int quotient = binaryToInt(num1) / binaryToInt(num2);
    intToBinary(quotient, result);
    if (sign1 * sign2 == -1) { // 如果两个数的符号不同
        // 结果为负数
        memmove(result + 1, result, strlen(result) + 1); // 移动字符数组
        result[0] = '-';
    }
}

int main() {
    char num1[MAX_LEN], num2[MAX_LEN], result[MAX_LEN];
    printf("请输入第一个大整数：");
    scanf("%s", num1);
    printf("请输入第二个大整数：");
    scanf("%s", num2);
    printf("两个大整数的和为：");
    add(num1, num2, result);
    removeLeadingZeros(result);
    printf("%s\n", result);
    printf("两个大整数的差为：");
    subtract(num1, num2, result);
    removeLeadingZeros(result);
    printf("%s\n", result);
    printf("两个大整数的积为：");
    multiply(num1, num2, result);
    removeLeadingZeros(result);
    printf("%s\n", result);
    printf("两个大整数的商为：");
    divide(num1, num2, result);
    removeLeadingZeros(result);
    printf("%s\n", result);
    return 0;
}

代码解释

1. intToBinary(int num, char binary[]) 函数将整型 num 转换为二进制字符数组表示，并存放到 binary 数组中。函数首先判断 num 的符号，如果是负数，则在数组开头添加一个 '-' 字符。然后，函数通过不断取余和除以 2 的操作，将 num 的每一位提取出来，并将其转换为字符形式存放到数组中。最后，函数将数组中的字符反转，使其从低到高位依次存放。

2. binaryToInt(char binary[]) 函数将二进制字符数组表示的大整数转换为整型。函数首先判断数组的符号，如果是负数，则设置 sign 为 -1。然后，函数依次遍历数组中的每个字符，将其转换为数字，并将其乘以 2 的相应次幂，最后将所有数字相加得到最终结果。

3. getSign(char num[]) 函数获取大整数的符号。如果数组的第一个字符为 '-'，则返回 -1，否则返回 1。

4. removeLeadingZeros(char num[]) 函数去除大整数前面的 0。函数通过循环遍历数组，找到第一个非 0 字符的位置，然后将该位置之后的字符移动到数组的开头。

5. add(char num1[], char num2[], char result[]) 函数实现大整数加法运算。函数首先判断两个数的符号，如果符号相同，则将两个数转换为整型，相加后再转换为二进制字符数组。如果符号不同，则将两个数的符号取反，然后做减法。

6. subtract(char num1[], char num2[], char result[]) 函数实现大整数减法运算。函数首先判断两个数的符号，如果被减数为负数，则将其符号取反，再做加法。如果减数为负数，则将其符号取反，再做加法。如果两个数的符号相同，则将两个数转换为整型，相减后再转换为二进制字符数组。

7. multiply(char num1[], char num2[], char result[]) 函数实现大整数乘法运算。函数首先将两个数转换为整型，相乘后再转换为二进制字符数组。如果两个数的符号不同，则结果为负数。

8. divide(char num1[], char num2[], char result[]) 函数实现大整数除法运算。函数首先将两个数转换为整型，相除后再转换为二进制字符数组。如果两个数的符号不同，则结果为负数。

总结

本文介绍了使用 C 语言实现大整数运算的二进制字符数组表示法，并提供了详细的代码示例和注释。该方法通过将大整数转换为二进制形式，并存储在字符数组中，避免了整数溢出问题，并实现了加减乘除等基本运算。这种方法对于处理超大整数的运算非常有效。