计算一个非常大的整数

Question

如何添加两个大整数，我尝试过使用数组，但仍然有一些错误。 例如：23 位 + 25 位正整数 (2345235... + 34634235....)

我尝试过使用数组来分隔数字并最终将它们相加，但仍然存在一些错误，例如当 999 + 999 时，它会输出 998，或者当它是 24 位 + 25 位时，代码变得复杂。有什么简单的方法可以做到吗？

#include <stdio.h>

int main(void)
{
    int length_A, length_B, times;
    long long int A[101] = {0};
    long long int B[101] = {0};
    long long int total[101] = {0};

    scanf("%d", &length_A);
    for (int i = 0; i < length_A; i++)
    {
        scanf("%1lld", &A[i]);
    }
    scanf("%d", &length_B);
    for (int j = 0; j < length_B; j++)
    {
        scanf("%1lld", &B[j]);
    }

    if (length_A > length_B)
    {
        times = length_A - length_B;
        for (int l = 0; l < times; l++)
        {
            total[l] = A[l];
        }
        for (int k = 0; k < length_B; k++)
        {
            total[k+times] = A[k+times] + B[k];
            if(total[k+times] > 9)
            {
                if (total[k+times-1] == 9)
                {
                    total[k+times-2]++;
                    total[k+times-1] = 0;
                    total[k+times] -= 10;
                }
                else if (total[k+times-1] < 9)
                {
                    total[k+times-1]++;
                    total[k] -= 10;
                }
            }
        }
        for (int z = 0; z < length_B; z++)
        {
            printf("%lld", total[z]);
        }
    }
    else if (length_B > length_A)
    {
        times = length_B - length_A;
        for (int k = 0; k < length_B; k++)
        {
            for (int l = 0; l < times; l++)
            {
                total[l] = B[l];
            }
            total[k+times] = A[k] + B[k+times];
            if(total[k] > 9)
            {
                if (total[k-times] == 9)
                {
                    total[k-times-1]++;
                    total[k-times] = 0;
                    total[k] -= 10;
                }
                else
                {
                    total[k-1]++;
                    total[k] -= 10;
                }
            }
        }
        for (int z = 0; z < length_B; z++)
        {
            printf("%lld", total[z]);
        }
    }
    else
    {
        for (int k = 0; k < length_B; k++)
        {
            total[k] = A[k] + B[k];
            if(total[k] > 9)
            {
                if (total[k-1] == 9)
                {
                    total[k-2]++;
                    total[k-1] = 0;
                    total[k] -= 10;
                }
                else
                {
                    total[k-1]++;
                    total[k] -= 10;
                }
            }
        }
        for (int z = 0; z < length_B; z++)
        {
            printf("%lld", total[z]);
        }
    }
}

Answer 1

• OP 的代码从最重要到最不重要添加。从最不重要（最高索引）到最重要的位置添加并跟踪进位更容易且更常见。

 // General algorithm.  Needs more work to handle if the lengths of a, b differ.
 carry = 0;
 for (index = least; index >= most; index--) {
   sum = a[index] + b[index] + carry;
   total[index] = sum %10;
   carry = sum / 10;
 }

• OP 的代码不会处理两个数字之和形成最高有效数字的进位。事实上，它试图设置

  total[-1] = ...

  。

// After the above loop
if (carry) {
  // Shift sum digits "right"
  // Then set the new most significant digit.
}

• total

  数组应比

  A

  、

  B

  长1，以处理潜在的最后一个“进位”。

• long long int A[101] = {0};

  太过分了。

  signed char A[101] = {0};

  就足够了。

---

有什么简单的方法吗？

也许，对某些人来说容易，对学习者来说是一个挑战。

考虑将输入与加法和输出分开。由 3 个功能组成。

// Return length
int big_number_read(int max_length, signed char *destination);

// Return length
int big_number_add(int max_sum_length, signed char *sum, 
    int a_length, signed char *a, 
    int b_length, signed char *b);

void big_number_print(int a_length, signed char *a);