Chinaunix首页 | 论坛 | 博客
  • 博客访问: 541814
  • 博文数量: 138
  • 博客积分: 0
  • 博客等级: 民兵
  • 技术积分: 1084
  • 用 户 组: 普通用户
  • 注册时间: 2014-03-17 14:32
个人简介

小公司研发总监,即当司令也当兵!

文章分类

全部博文(138)

分类: LINUX

2018-02-27 10:36:55

    首先说一下乘法计算的算法:同样是模拟人工计算时的方法。
    从低位向高位乘,在竖式计算中,我们是将乘数第一位与被乘数的每一位相乘,记录结果之后,用第二位相乘,记录结果并且左移一位,以此类推,直到计算完最后一位,再将各项结果相加,得出最后结果。
下图是 123*456 的乘法竖式:



竖式低位在右边,计算从由到左,与我们平常计算机计算顺序不符;我将两个数字倒序,得到如下算式(从左到右):


由上图可见,乘法过程

即一个数的第i 位和另一个数的第j 位相乘所得的数,一定是要累加到结果的第i+j 位上

即:ans[i+j] = a[i]*b[j];

另外进位时要处理,当前的值加上进位的值再看本位数字是否又有进位。

简单实现(64bit 两数相乘, 更多位数,只需要调整存储buf的长度即可):


点击(此处)折叠或打开

  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <string.h>


  4. static char* muilt_b(char* n1, char* n2)
  5. {
  6.     static char ret[129] = {0};
  7.     char rn1[129] = {0};
  8.     char rn2[129] = {0};
  9.     int i,j;
  10.     int len1, len2;

  11.     int carry, sum, rcd[128] = {0};

  12.     memset(ret, '0', 128);
  13.     memset(rn1, '0', 128);
  14.     memset(rn2, '0', 128);

  15.     len1 = strlen(n1);
  16.     len2 = strlen(n2);

  17.     for (i = 0; i < len1; i++)
  18.         rn1[i] = n1[len1 - 1 - i];

  19.     for (j = 0; j < len2; j++)
  20.         rn2[j] = n2[len2 - 1 - j];

  21.     for (i = 0; i < len1; i++)
  22.     {
  23.         for (j= 0; j < len2; j++)
  24.             rcd[i+j] += (rn1[i] - '0') * (rn2[j] - '0');
  25.     }

  26.     carry = 0;
  27.     for (i = 0; i < 128;i++)
  28.     {
  29.         sum = rcd[i] + carry;
  30.         rcd[i] = sum % 10;
  31.         carry = sum / 10;

  32.         ret[i] = rcd[i] + '0';
  33.     }


  34.     for (i = strlen(ret) -1; i >= 0; i--)
  35.     {
  36.         if (ret[i] == '0')
  37.             ret[i] = '\0';
  38.         else
  39.             break;
  40.     }

  41.     len1 = strlen(ret);
  42.     for (i = 0; i <= len1 / 2; i++)
  43.     {
  44.         j = ret[i];
  45.         ret[i] = ret[len1 -1 - i];
  46.         ret[len1 -1 -i] = j;
  47.     }
  48.     return ret;
  49. }


阅读(1446) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~