算法理解之大数相乘问题

所谓大数相乘，就是指数字比较大，相乘的结果超出了基本类型的表示范围，所以这样的数不能够直接做乘法运算。

其实乘法运算可以分拆为两步：第一步，是将乘数与被乘数逐位相乘；第二步，将逐位相乘得到的结果，对应相加起来。这有点类似小学数学中，计算乘法时通常采用的“竖式运算”。

这里唯一要注意的便是进位问题，我们可以先不考虑进位，当所有位对应相加，产生结果之后，再考虑如果该位的数字大于10，那么我们用取余运算，在该位上只保留取余运算的结果，而将进位（通过模运算得到）累加到下一位便可。

注：大数a和大数b相乘结果位数为aLen+bLen（最高位有进位）或者aLen+bLen-1（最高位无进位），aLen和bLen分别为数a和数b的长度，另外相乘结果result[i + j] = a[i] * b[j]; 

自己实现代码如下：

#include <stdio.h>  
#include <string.h>  
#include <stdlib.h>  
  
  
void Multiply(char *a, char *b, char *result)  
{  
    int i, j, aLen, bLen, sLen, *s;  
  
    aLen = strlen(a);  
    bLen = strlen(b);  
  
    sLen = sizeof(int) * (aLen + bLen);  
  
    s = (int *)malloc(sLen);  
  
    memset(s, 0, sLen);  
  
    //a的每一位分别乘以b的每一位，并把最终结果对应位置上的数值累加，可能该位置上的数字大于10  
    for(i = 0; i < aLen; i++)  
    {  
        for(j = 0; j < bLen; j++)  
        {  
            //s数组位i+j+1是为防止结果长度为aLen + bLen -1时（即最高位无进位），最后一位补充0，结果出错  
            s[i + j + 1] += (a[i] - '0') * (b[j] - '0');  
        }  
    }  
  
    //把最终结果 有一位置上为大于10的数字 向前进位  
    for(i = aLen + bLen; i >= 0; i--)  
    {  
        if(s[i] >= 10)  
        {  
            s[i - 1] += s[i]/10;  
            s[i] = s[i]%10;  
        }  
    }  
  
    i = 0;  
    //如果最高位无进位时则从s[1]开始赋值给result  
    while(s[i] == 0)  
    {  
        i++;  
        //防止乘数或者被乘数有0存在，结果为0这样可以打印出0  
        if(s[i] == 0)  
        {  
            result[0] = '0';  
            free(s);  
            return;  
        }  
  
    }  
  
    for(j = 0; i < aLen + bLen; i++, j++)  
    {  
        result[j] = s[i] + '0';  
    }  
    result[j] = '';  
  
    free(s);  
}  
  
int main(int argc, char* argv[])  
{  
    int i = 0;  
    char a[] = "123";  
    char b[] = "456";  
    char c[100] = {0};  
  
    Multiply(a, b, c);  
  
    for(int i = 0; i < sizeof(c); i++)  
    {  
        printf("%c ", c[i]);  
    }  
    printf("
");  
  
    return 0;  
}