面试官让你用C语言实现大数相乘，慌吗？
在之前的笔试题解析里面，我写了大数相加的问题，这里再剖析一个大数相乘，顾名思义，大数相乘就是这个数已经大到最大的数据类型都没有办法保存了。
我们看看最大的数据类型可以保存多大的数据。
#include 'stdio.h'
#include 'string.h'
int main()
{
printf('0~%llu\n',(1ULL << sizeof(unsigned long long)*8) -1);
return 0;
}
代码输出：
0~18446744073709551615所以如果我们的数大于18446744073709551615 就会存在没有一个数据类型可以存储的情况，所以会有大数相乘的问题。
如何解决大数相乘问题？
看我下面的解题思路，这个思路可以也是从网上看到的。
我们拿乘数的最低位，也就是 2358中的8 依次乘以被乘数的每一位，然后不做进位处理得到8 16 32 40.继续拿十位，百位，千位相乘，还是不进位 然后依次列相加，相加的时候，也不做进位处理得到一个数据 2 7 19 40 51 57 40.后面循环对上一步得到的数据进行进位处理，就会得到最终的结果。
代码实现
#include 'stdio.h'
#include 'string.h'
#define char_to_int(a) (int) (a - '0')
#define int_to_char(a) (char)(a + '0')
int main()
{
char a[1000]={'1245'};
char b[1000]={'2358'};
char c[1000]={0};
int i = 0, j = 0, k = 0;
memset(c,0,sizeof(c));
printf('%ld\n',strlen(a)-1);
printf('%ld\n',strlen(b)-1);
/*完成图片中的1，2步，结果从数组开头开始存放*/
for (i = 0; i<strlen(a); i++)
{
k = i;
for (j = 0; j<strlen(b); j++){
c[k] += char_to_int(a[i]) * char_to_int(b[j]);
k++;
}
}
printf('k=%d \n%.2d %.2d %.2d %.2d %.2d %.2d %.2d\n',k,c[0],c[1],c[2],c[3],c[4],c[5],c[6]);
/*完成图片中的3步,从后面往前面*/
for (i = k-1; i>0; i--)
{
if (c[i] >= 10) {
c[i-1] = c[i]/10 + c[i-1];
c[i] = c[i]%10;
printf('%.2d %.2d %.2d %.2d %.2d %.2d %.2d\n',c[0],c[1],c[2],c[3],c[4],c[5],c[6]);
}
}
/*输出*/
for(i=0;i<k;i++)
printf('%d',c[i]);putchar('\n');
return 0;
}
我这个代码直接参照我上面的图片例程编写，比较有参考性，大家在看代码的时候也需要注意一些细节，比如strlen获取的长度，k变量的大小等等。
程序输出：
33k=702 07 19 40 51 57 4002 07 19 40 51 61 0002 07 19 40 57 01 0002 07 19 45 07 01 0002 07 23 05 07 01 0002 09 03 05 07 01 002935710随机验证下代码
验证的时候发现上面写的代码还有一些问题，顺便修改了下
#include 'stdio.h'
#include 'string.h'
#define char_to_int(a) (int) (a - '0')
#define int_to_char(a) (char)(a + '0')
int main()
{
char a[1000]={'1561591985156415641419841516515919'};
char b[1000]={'45645689129812561564159129821985125641'};
unsigned long long c[1000]={0};
int i = 0, j = 0, k = 0;
memset(c,0,sizeof(c));
/*完成图片中的1，2步，结果从数组开头开始存放*/
for (i = 0; i<strlen(a); i++)
{
k = i;
for (j = 0; j<strlen(b); j++){
c[k] += char_to_int(a[i]) * char_to_int(b[j]);
k++;
}
}
/*完成图片中的3步,从后面往前面*/
for (i = k-1; i>0; i--)
{
if (c[i] >= 10) {
c[i-1] = c[i]/10 + c[i-1];
c[i] = c[i]%10;
}
}
/*输出*/
for(i=0;i<k;i++)
printf('%llu',c[i]);putchar('\n');
return 0;
}
代码输出：
71279942302056620434200279768171066840415273983925010258196655791579079但是遗憾的是，电脑自带的计算器不能计算这么大的数据，所以，我也不知道这个计算结果是不是正确的。
所以计算一个计算器可以计算的值
#include 'stdio.h'
#include 'string.h'
#define char_to_int(a) (int) (a - '0')
#define int_to_char(a) (char)(a + '0')
int main()
{
char a[1000]={'1844674407'};
char b[1000]={'3709551615'};
unsigned long long c[1000]={0};
int i = 0, j = 0, k = 0;
memset(c,0,sizeof(c));
/*完成图片中的1，2步，结果从数组开头开始存放*/
for (i = 0; i<strlen(a); i++)
{
k = i;
for (j = 0; j<strlen(b); j++){
c[k] += char_to_int(a[i]) * char_to_int(b[j]);
k++;
}
}
/*完成图片中的3步,从后面往前面*/
for (i = k-1; i>0; i--)
{
if (c[i] >= 10) {
c[i-1] = c[i]/10 + c[i-1];
c[i] = c[i]%10;
}
}
/*输出*/
for(i=0;i<k;i++)
printf('%llu',c[i]);putchar('\n');
return 0;
}
程序输出：
6842914925636017305计算器输出
好吧，再来一次
#include 'stdio.h'
#include 'string.h'
#define char_to_int(a) (int) (a - '0')
#define int_to_char(a) (char)(a + '0')
int main()
{
char a[1000]={'184467'};
char b[1000]={'3709551615'};
unsigned long long c[1000]={0};
int i = 0, j = 0, k = 0;
memset(c,0,sizeof(c));
/*完成图片中的1，2步，结果从数组开头开始存放*/
for (i = 0; i<strlen(a); i++)
{
k = i;
for (j = 0; j<strlen(b); j++){
c[k] += char_to_int(a[i]) * char_to_int(b[j]);
k++;
}
}
/*完成图片中的3步,从后面往前面*/
for (i = k-1; i>0; i--)
{
if (c[i] >= 10) {
c[i-1] = c[i]/10 + c[i-1];
c[i] = c[i]%10;
}
}
/*输出*/
for(i=0;i<k;i++)
printf('%llu',c[i]);putchar('\n');
return 0;
}
程序输出
684289857764205计算器输出
嗯，好像没有问题。
其他的大数相乘算法
我上面的代码不是最优解，但是可以让大家理解这个过程，如果想了解比较优秀的解决方案，可以网上找找资料。
https://en.wikipedia.org/wiki/Sch%C3%B6nhage%E2%80%93Strassen_algorithm
https://blog.csdn.net/u010983881/article/details/77503519