[笔记]一道C语言面试题：大整数乘法

题目：输入两个数字字符串，如“1234567890”和“987654321”，返回二者相乘的结果字符串，如本例返回为“1219326311126352690”。

来源：某500强企业面试题目

思路：从尾部到头部，对两个字串的每个数字分别相乘，并放入结果字符串相应的位置。

#include "stdio.h"
#include "stdlib.h"
#include "string.h"

char *BigNumMultiply(const char *n1, const char *n2)
{
    // quit if n1 or n2 is invalid
    if (!n1 || !n2) {
        return NULL;
    }

    // get length
    int Len1 = strlen(n1);
    int Len2 = strlen(n2);
    int Len = Len1 + Len2;

    // allocate result buffer
    char *ret = (char *)malloc(Len + 1);
    if (!ret) {
        return NULL;
    }
    memset(ret, 0, Len + 1);

    // multiply
    for (int i = Len1 - 1; i >= 0; --i) {
        for (int j = Len2 - 1; j >= 0; --j) {
            int k = i + j + 1;
            // multiply digit by digit
            ret[k] += (n1[i] - '0') * (n2[j] - '0');
            
            // add to upper position
            if (ret[k] >= 10){
                ret[k - 1] += ret[k] / 10;
                ret[k] = ret[k] % 10;
            }
        }
    }

    // handle first 0
    int d = ret[0] == 0 ? 1 : 0;
    for (int i = 0; i < Len - d; ++i) {
        ret[i] = ret[i + d] + '0';
    }
    ret[Len - d] = '

[笔记]一道C语言面试题：大整数乘法

相关推荐