假如說我們有兩個(gè)很大的數(shù)相乘，比如說兩個(gè)二十位數(shù)相乘，我們用程序該怎么實(shí)現(xiàn)呢？在c語(yǔ)言中，int類型的變量大小一般是4byte，肯定是存不下這么大的數(shù)的。這篇文章來稍微討論下這個(gè)問題。

既然變量存不下這么大的數(shù)，那么我們可以用數(shù)組來存儲(chǔ)，比如說789，我們可以用char a[4] = "789"來存儲(chǔ)，這樣的話就可以存下很大的數(shù)了。

下一步就是如何解析數(shù)組并實(shí)現(xiàn)乘法。關(guān)于乘法，我們小時(shí)候都學(xué)過筆算，所以，我們就可以根據(jù)這個(gè)筆算的方法來實(shí)現(xiàn)。

舉個(gè)例子：

比如說我們計(jì)算1256*23

第一步：

3*1256=3768，
2*1256=2512

第二步：

25120+3768=28888

下面我們用代碼來實(shí)現(xiàn)一下

#include 
#include 
#include 


int main()
{
    char data[256] = {0};
    int mult1_size = 0;
    int mult2_size = 0;
    char *mult1 = NULL;
    char *mult2 = NULL;


    printf("Please input mult1:\\n");
    fgets(data, 256, stdin);
    mult1_size = strlen(data) - 1;
    data[mult1_size] = '\\0';
    mult1 = (char *)malloc(mult1_size + 1 + 1); // +1 for carry, +1 is '\\n' for printf
    memset(mult1, 0, mult1_size + 1 + 1);
    memcpy(mult1, data, mult1_size);


    memset(data, 0, 256);
    printf("Please input mult2:\\n");
    fgets(data, 256, stdin);
    mult2_size = strlen(data) - 1;
    data[mult2_size] = '\\0';
    mult2 = (char *)malloc(mult2_size + 1 + 1);
    memset(mult2, 0, mult2_size + 1 + 1);
    memcpy(mult2, data, mult2_size);


    //printf("mult1 = %s, mult2 = %s\\n", mult1, mult2);


    char sum_ret_row = mult1_size+1+1; //行
    char sum_ret_col = mult2_size+1+1; //列
    char *sum_ret = (char *)malloc(sum_ret_row * sum_ret_col);


    for (int i = mult2_size - 1; i >= 0; i--) {
        char reserve = 0;
        int sum_ret_i = 0;
        for (int j = mult1_size - 1; j >= 0; j--) {
            int m1 = mult1[j] - '0';
            int m2 = mult2[i] - '0';
            int value = m1 * m2 + reserve;
            //printf("%d * %d = %d\\n", m1, m2, value);


            sum_ret[sum_ret_row * i + sum_ret_i++] = (value % 10) + '0';


            if (value > 9) reserve = value / 10;
            else reserve = 0;
        }
        if (reserve != 0) {
            sum_ret[sum_ret_row * i + sum_ret_i++] = reserve + '0';
        }
    }


    // printf("ret=\\n");
    // for (int i = mult2_size - 1; i >= 0; i--) {
    //     int len = strlen(&sum_ret[i * sum_ret_row]);
    //     for (int j = len - 1; j >= 0; j--) {
    //         printf("%c", sum_ret[i*sum_ret_row+j]);
    //     }
    //     printf("\\n");
    // }


    char out[256] = {0};
    int out_i = 0;
    for (int i = mult2_size - 1; i > 0; i--) {
        static int copy = 0;
        if (copy == 0) {
            copy++;
            memcpy(out, &sum_ret[i * sum_ret_row], strlen(&sum_ret[i * sum_ret_row]));
        }


        out_i++;
        int reserve = 0;
        int len = strlen(&sum_ret[(i - 1) * sum_ret_row]);
        for (int j = 0; j < len; j++) {
            int add1 = out[out_i + j] == 0 ? 0 : out[out_i + j] - '0';
            int add2 = sum_ret[(i - 1) * sum_ret_row + j] - '0';
            int value = add1 + add2 + reserve;
            //printf("%d=%d+%d+%d\\n", value, add1, add2, reserve);


            out[out_i + j] = (value % 10) + '0';
            //printf("%c\\n", out[out_i + j]);


            if (value > 9) reserve = value / 10;
            else reserve = 0;
        }
        if (reserve != 0) {
            out[out_i + len - 1] = reserve + '0';
        }
    }


    //reverse
    int len = strlen(out);
    for (int j = 0; j < len / 2; j++) {
        char tmp = out[j];
        out[j] = out[len - 1 - j];
        out[len - 1 - j] = tmp;
    }


    printf("%s * %s = %s\\n", mult1, mult2, out);


    free(mult1);
    free(mult2);
    free(sum_ret);


    return 0;
}

其實(shí)代碼的思想就和上面說的一樣，運(yùn)行一下

Please input mult1:
123456789654123456798
Please input mult2:
451216557522365512323
123456789654123456798 * 451216557522365512323 = 55705747630496376206760849965779027121754

可以看見，兩個(gè)二十一位數(shù)相乘，我們的程序依然算出了結(jié)果，經(jīng)過實(shí)驗(yàn)，結(jié)果正確。

審核編輯：劉清