个人简介
小公司研发总监，既当司令也当兵！
文章分类
相关博文
- ·
- ·
- ·
- ·
- ·
- ·
- ·
- ·
- ·
- ·
分类： linux
2018-02-27 10:36:55
首先说一下乘法计算的算法：同样是模拟人工计算时的方法。
从低位向高位乘，在竖式计算中，我们是将乘数第一位与被乘数的每一位相乘，记录结果之后，用第二位相乘，记录结果并且左移一位，以此类推，直到计算完最后一位，再将各项结果相加，得出最后结果。
下图是 123*456 的乘法竖式：
竖式低位在右边，计算从由到左，与我们平常计算机计算顺序不符；我将两个数字倒序，得到如下算式（从左到右）：
由上图可见，乘法过程：
即一个数的第i 位和另一个数的第j 位相乘所得的数，一定是要累加到结果的第i j 位上
从低位向高位乘，在竖式计算中，我们是将乘数第一位与被乘数的每一位相乘，记录结果之后，用第二位相乘，记录结果并且左移一位，以此类推，直到计算完最后一位，再将各项结果相加，得出最后结果。
下图是 123*456 的乘法竖式：
竖式低位在右边，计算从由到左，与我们平常计算机计算顺序不符；我将两个数字倒序，得到如下算式（从左到右）：
由上图可见，乘法过程：
即一个数的第i 位和另一个数的第j 位相乘所得的数，一定是要累加到结果的第i j 位上
即：ans[i j] = a[i]*b[j];
另外进位时要处理，当前的值加上进位的值再看本位数字是否又有进位。
简单实现（64bit 两数相乘， 更多位数，只需要调整存储buf的长度即可）：点击(此处)折叠或打开
-
#include <stdio.h>
-
#include <stdlib.h>
-
#include <string.h>
-
-
-
static char* muilt_b(char* n1, char* n2)
-
{
-
static char ret[129] = {0};
-
char rn1[129] = {0};
-
char rn2[129] = {0};
-
int i,j;
-
int len1, len2;
-
-
int carry, sum, rcd[128] = {0};
-
-
memset(ret, '0', 128);
-
memset(rn1, '0', 128);
-
memset(rn2, '0', 128);
-
-
len1 = strlen(n1);
-
len2 = strlen(n2);
-
-
for (i = 0; i < len1; i)
-
rn1[i] = n1[len1 - 1 - i];
-
-
for (j = 0; j < len2; j)
-
rn2[j] = n2[len2 - 1 - j];
-
-
for (i = 0; i < len1; i)
-
{
-
for (j= 0; j < len2; j)
-
rcd[ij] = (rn1[i] - '0') * (rn2[j] - '0');
-
}
-
-
carry = 0;
-
for (i = 0; i < 128;i)
-
{
-
sum = rcd[i] carry;
-
rcd[i] = sum % 10;
-
carry = sum / 10;
-
-
ret[i] = rcd[i] '0';
-
}
-
-
-
for (i = strlen(ret) -1; i >= 0; i--)
-
{
-
if (ret[i] == '0')
-
ret[i] = '\0';
-
else
-
break;
-
}
-
-
len1 = strlen(ret);
-
for (i = 0; i <= len1 / 2; i)
-
{
-
j = ret[i];
-
ret[i] = ret[len1 -1 - i];
-
ret[len1 -1 -i] = j;
-
}
-
return ret;
- }
给主人留下些什么吧！~~