如何为大整数实现整数数组加法器？

Question

由于 C 不支持大整数 JAVA，我正在尝试实现一个整数加法器函数，该函数将两个整数数组作为参数，returns 指向它们总和的指针又是数组。这是我的代码。

#include<stdio.h>
#include<stdlib.h>
int max(int a,int b) {
    return a < b ? b : a;
}

int* decimalAdder (int* p, int* q) {
    int size1, size2, i;
    size1 = sizeof(p) / sizeof(int);
    size2 = sizeof(q) / sizeof(int);
    int m = max(size1, size2) + 1;
    int* c = (int*)malloc(m * sizeof(int));
    int carry = 0;
    for(i=0 ; i<m ; i++) {
        c[i] = 0;
        if(i < size1 && i < size2) {
            c[i] += p[i] + q[i] + carry;
            if(c[i] >= 10) {
                c[i] = c[i] % 10;
                carry = 1;
            }
            else
                carry = 0;
        }
        else if(i < size1) {
            c[i] += p[i] + carry;
            if(c[i] >= 10) {
                c[i] = c[i] % 10;
                carry = 1;
            }
            else
                carry = 0;
        }
        else if(i < size2) {
            c[i] += q[i] + carry;
            if(c[i] >= 10) {
                c[i] = c[i] % 10;
                carry = 1;
            }
            else
                carry = 0;
        }
        else
            c[i] += carry;
    }
    return c;
}

//Test program
int main() {
    int a[] = {7, 5, 3, 6};
    int b[] = {3, 5, 3};
    int* sum;
    int i;
    sum = decimalAdder(a, b);
    int size = sizeof(sum) / sizeof(int);
    for(i = size ; i >= 0 ; i--)
        printf("%d", sum[i]);
    free(sum);
    sum=NULL;
    return 0;
}

输出10 我哪里错了？我错过了什么？

Answer 1

But how to determine the true sizes of p and q if it is unknown?

像这样：

#include<stdio.h>

void returnLen(int length){
    printf("The length of Array is:\t%d\n",length);
}

int main(void){
    int array[] = {7, 5, 3, 6, 1, 9, 3, 6, 2, 10, 55};
    int length = sizeof array / sizeof array[0];

    returnLen(length);
    return 0;
}

输出：

The length of Array is: 11

Answer 2

如评论中所述，sizeof(p) 和 sizeof(q) 与 sizeof(int *) 相同。您需要将真实的数组大小作为参数传递给 decimalAdder().

所以首先，更改 decimalAdder() 以接收尺寸：

int *decimalAdder (int *p, size_t size1, int *q, size_t size2) {
    int i;
    int m = max(size1, size2) + 1;
    int *c = malloc(m * sizeof(int));
    /* ... */
}

你问如何确定传递给decimalAdder()的数组的大小。好吧，如果你动态分配数组，那么你可能知道大小（它与你之前传递给 malloc(3) 的大小相同）。

如果数组是堆栈分配的（这里就是这种情况），您可以使用在 main() 中使用的 sizeof() 方法，但只能在声明数组的函数内部使用（因为一旦将局部数组传递给另一个函数，它就会衰减为指向第一个元素的指针，您无法再确定其大小。

所以在这种情况下，您可以将 main() 更改为：

int main(void) {
    int a[] = {7, 5, 3, 6};
    int b[] = {3, 5, 3};
    size_t size1 = sizeof(a)/sizeof(a[0]);
    size_t size2 = sizeof(b)/sizeof(b[0]);
    int* sum;
    int i;
    sum = decimalAdder(a, size1, b, size2);    
    int size = max(size1, size2);

    for(i = size ; i >= 0 ; i--)
        printf("%d", sum[i]);

    free(sum);
    sum=NULL;

    return 0;
}

请注意，int size = sizeof(sum) / sizeof(int); 不会按您预期的方式工作：sum 不是真正的数组，它是指向 int 的指针，因此 sizeof(sum) 是与 sizeof(int *) 相同， 而不是 您分配的数组的大小。 C 不会跟踪它，你必须自己做（而不是 Java）。

Answer 3

因为 C 中的整数数组是一种简单类型，所以在一般情况下它不会随附有关其大小的信息。有许多方法可以解决这个问题。 Michi 的答案对于静态分配的数组是正确的，如果您始终知道您将使用多少数组元素，那么这可能足以满足您的需求。但是，如果是这种情况，那么整个练习就没有实际意义了，因为您可以只使用宏化常量并获得相同的结果。

最终您将要做的是创建一个数据结构，该数据结构可用于携带位数（或多位数元素）。根据此代码的使用方式，类似这样的方法可能有效：

struct myArray{
    int length;
    int *digits;
};

这意味着您必须管理结构的内存（分配、释放、调整大小等）。此外，您可以考虑使用 #include 和 int64_t 或 uint64_t 作为数组元素，因为您将能够使用更少的单元格来表示给定的大整数。

数据结构（上图）绝不是唯一的解决方案。您也可以使用链表（尽管如果您要做的只是在节点上进行简单的算术运算，那将是相当重量级的）。

如何为大整数实现整数数组加法器？

How to implement a Integer Array Adder for big integers?

c

arrays

integer

add

biginteger