如何在C中使用char数组添加两个大的非负整数？

Question

我正在制作一个程序来添加两个大的非负整数（每个大整数最多包含100个数字）。然而，在我的程序中，它为大多数情况提供了错误的输出。

我已经完成了main()函数，但我相信我的代码问题在AddTwoBigNumbers()函数内。

#include <stdio.h>

const int MAX_INT_LENGTH = 100;

void AddTwoBigNumbers(char bigN[], char bigM[], char sum[]) {
    int i = 0;
    int index = 0;
    int count = 0;
    int index2 = 0;
    while (1) {
        int sum1 = count;
        if (bigM[index]) {
            sum1 += bigM[index] - '0';
            index++;
        }
        if (bigN[index2]) {
            sum1 += bigN[index2] - '0';
            index2++;
        }
        sum[i] = sum1 % 10 + '0';
        i++;
        count = sum1 / 10;
        if (bigM[index] == 0 && bigN[index2] == 0) {
            break;
        }
    }
    if (count) {
        sum[i] = count + '0';
        i++;
    }
    sum[i] = 0;

    int x, len = 0;
    for (x = 0; sum[x]; ++x) {
        ++len;
    }

    for (x = 0; x < len / 2; ++x) {
        sum[len] = sum[x];
        sum[x] = sum[len - x - 1];
        sum[len - x - 1] = sum[len];
    }
}

int main() {
    char bignum[2][MAX_INT_LENGTH]; // bignum[0] and bignum[1] are to store the digits of the two input number
    char sum[MAX_INT_LENGTH + 1];     // to store the sum of the two big numbers

    // read in two numbers
    scanf("%s", bignum[0]);
    scanf("%s", bignum[1]);

    // calculate sum of the two numbers
    AddTwoBigNumbers(bignum[0], bignum[1], sum);

    // display the sum on screen
    printf("%s\n", sum);

    return 0;
}

样本案例如下：

输入：

1
999999999999999999999999999

输出：

1000000000000000000000000000

我的输出：

1000000000000000000000000000

输入：

999999999999999999999999999
999999999999999999999999999

输出：

1999999999999999999999999998

我的输出：

1999999999999999999999999989

Answer 1

在您发布的程序中，您首先考虑的是最重要的数字。

首先尝试考虑最低有效数字，然后朝着更有效的数字方向前进。

考虑可能生成的进位值并将其添加到下一组值并相应地重置进位值。

请记住，这些数字被视为字符。当您需要整数值时，从字符中减去'0'，并通过添加'0'将它们转换回字符形式。

调整bigM和bigN长度不一样的情况。

如果bigM的所有数字都结束，请使用bigN的值和进位值（如果有的话）来计算sum的所有剩余数字，反之亦然。

最后，在输入数字的所有数字都用尽之后，检查是否有剩余的进位并将其添加到sum。

您可以以相反的方式计算并向sum插入值，如果您愿意，可以稍后反转字符串。

不要忘记nul（'\0'）最后终止sum。

---

你可以做点什么

void AddTwoBigNumbers(char bigN[], char bigM[], char sum[])
{
    int i=strlen(bigM)-1, j=strlen(bigN)-1, k, carry=0;
    for(k=0; i>=0 && j>=0; --i, --j, ++k)
    {
        sum[k] = (bigM[i]-'0' + bigN[j]-'0' + carry)%10 + '0';
        carry = (bigM[i]-'0' + bigN[j]-'0' + carry)/10;
    }

    for(; i>=0; --i, ++k)
    {
        sum[k] = (bigM[i]-'0' + carry)%10 + '0'; 
        carry = (bigM[i]-'0' + carry)/10;
    }
    for(; j>=0; --j, ++k)
    {
        sum[k] = (bigN[j]-'0' + carry)%10 + '0'; 
        carry = (bigN[j]-'0' + carry)/10;
    }
    if(carry!=0)
    {
        sum[k++]=carry+'0';
    }
    sum[k]=0;

    //Reversing string
    for(int t=0; t<n/2; ++t)
    {
        char temp=sum[t];
        sum[t]=sum[n-1-t];
        sum[n-1-t]=temp;
    }
}

Answer 2

您的函数从左到右添加两个整数。试试这个方法，这是一个从后面添加到前面的算法（数组参数通常降级为指针，所以char *bigN在这里等于char bigN[]）：

void AddTwoBigNumbers(char *bigN, char *bigM, char* sum)
{
    int add = 0;
    int index = 0;
    int count = 0;
    int nbigN = strlen(bigN)-1;
    int nbigM = strlen(bigM)-1;
    while (nbigN >= 0 || nbigM >= 0)
    {
        int N = 0, M = 0;
        if (nbigN >= 0)
        {
            N = bigN[nbigN] - '0';
            nbigN--;
        }
        if (nbigM >= 0)
        {
            M = bigM[nbigM] - '0';
            nbigM--;
        }
        add = N + M + count;
        sum[index++] = add % 10 + '0';
        count = add / 10;
    }
    if (count)
        sum[index++] = count + '0';
    sum[index] = 0;
    int nsum = strlen(sum);
    for (int i = 0, j = nsum - 1; i < j; i++, j--)
    {
        char c = sum[i];
        sum[i] = sum[j];
        sum[j] = c;
    }
}

编辑：

int strlen(char* buf)
{
    int len = 0;
    if (buf == NULL)
        return len;
    while (*buf++)
        len++;
    return len;
}