C++实现大整数乘法（字符串乘法）

本文实例为大家分享了C++实现大整数乘法的具体代码，供大家参考，具体内容如下

#include<iostream>
#include<algorithm>
#include<string>
using namespace std;

string add(string a,string b)
{
 if(a.length()==0)
 return b;
 if(b.length()==0)
 return a;
 a.length()<b.length()?a.swap(b):a.length();

 reverse(a.begin(),a.end());
 reverse(b.begin(),b.end());
 int flag=0;
 for(int i=0;i<a.length();i++)
 {
 int aInt=a[i]-'0';
 int bInt=0;
 if(i<b.length())
  bInt=b[i]-'0';
 int result=aInt+bInt+flag;
 a[i]=result%10+'0';
 flag=result/10;
 }
 if(flag!=0)
 {
 a=a+(char)(flag+'0');
 }
 reverse(a.begin(),a.end());
 return a;
}
string multiply(std::string strMultiplierA,char x)
{
 int b=x-'0';
 int flag=0;
 for(int i=strMultiplierA.length()-1;i>=0;i--)
 {
 int a=strMultiplierA[i]-'0';
 int result=a*b+flag;
 strMultiplierA[i]=result%10+'0';
 flag=result/10;
 }
 if(flag!=0)
 strMultiplierA=(char)(flag+'0')+strMultiplierA;
 while(strMultiplierA.length()>1&&strMultiplierA[0]=='0')
 strMultiplierA=strMultiplierA.substr(1,strMultiplierA.length());
 return strMultiplierA;
}

/*****************************************************************************
 Prototype  : multiply
 Description : 两个任意长度的长整数相乘, 输出结果
 Input Param :
        const std::string strMultiplierA 乘数A
        const std::string strMultiplierB 乘数B
 Output    :
        std::string strRst      乘法结果
 Return Value :
        int            0 正确
                     -1 异常
*****************************************************************************/
int multiply (const std::string strMultiplierA,const std::string strMultiplierB, std::string &strRst)
{

  /* 在这里实现功能 */
  if(strMultiplierA.length()<=0||strMultiplierB.length()<=0)
 return -1;
 bool flag=false;//false"+" true"-"
 string strA=strMultiplierA,strB=strMultiplierB;
 if(strMultiplierA[0]=='-')
 {
 flag=~flag;
 strA=strMultiplierA.substr(1,strMultiplierA.length());
 }
 if(strMultiplierB[0]=='-')
 {
 flag==true?flag=false:flag=true;
 strB=strMultiplierB.substr(1,strMultiplierB.length());
 }

 for(int i=strB.length()-1;i>=0;i--)
 {
 string result=multiply(strA,strB[i]);
 int j=i;
 while(++j<strB.length())
  result=result+"0";
 // while(result.length()>1&&result[0]=='0')
 // result=result.substr(1,result.length());
 strRst=add(strRst,result);
 }
 while(strRst.length()>1&&strRst[0]=='0')
 strRst=strRst.substr(1,strRst.length());
 if(flag==true&&strRst!="0")
 strRst='-'+strRst;
  return 0;
}

int main()
{
 std::string strResult = "";

 multiply("-5489324", "0", strResult);

 cout<<strResult<<endl;
}

以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持我们。

赞 (0)

相关推荐

  • C++实现的大数相乘算法示例

    本文实例讲述了C++实现的大数相乘算法.分享给大家供大家参考,具体如下: 昨晚校招笔试,虐的没脸睡觉,能力太渣了,但我还在码农的坑里前行,希望早日跳坑,解决衣食住行之忧. 大数相乘,是指那些相乘结果或是乘数本身用long long类型都会溢出的数字,通常这些数字都通过string类型进行表示,借助于可动态调整大小的数据结构(vector,string,deque)模拟实现数字的乘法操作.对于普通的乘法,我们知道m位数和n位数相乘,最后的结果位数在区间内[m+n-1,m+n].例如34*56,我们

  • C++实现大数相乘算法

    C++实现大数相乘算法

    本文实例为大家分享了C++实现大数相乘的具体代码,供大家参考,具体内容如下 首先说一下乘法计算的算法:同样是模拟人工计算时的方法. 从低位向高位乘,在竖式计算中,我们是将乘数第一位与被乘数的每一位相乘,记录结果之后,用第二位相乘,记录结果并且左移一位,以此类推,直到计算完最后一位,再将各项结果相加,得出最后结果. 计算的过程基本上和小学生列竖式做乘法相同.为编程方便,并不急于处理进位,而将进位问题留待最后统一处理. 我们以125*53为例来说明计算过程: 1.先算125*3,3*5得到15个1,

  • 深入分析C++中两个大数相乘结果不正确的问题

    在编写代码做测试时发现两个大数相乘结果不正确的问题,测试代码如下: #include "stdafx.h"#include<stdlib.h>#include<time.h>int _tmain(int argc, _TCHAR* argv[]){      time_t temp1=1345172428000000;    time_t temp2=1345172428*1000000;   ::system("pause");    re

  • c++大数阶乘的实现方法

    C++代码如下: #include <algorithm>#include <vector>#include <cstdio>using namespace std;typedef  unsigned int Type;enum{ BASE_DATA = 10000, MAX_NUM = 100000 , MAX_SIZE = MAX_NUM+1000};struct MulOpt {Type data1;MulOpt(Type x):data1(x){}inline

  • C++实现大整数乘法

    算法竞赛入门经典 这本书并没有对大数乘法实现,所以自己补充了一下,乘法的实现很简单,就是再其数据结构基础上把每宽为8位的十进制数看成多项式的系数,vector的下标看成多项式的指数,然后再对应相乘相加就可以了,注意系数超过8位 将超八位的补分进位. 我这里是笛卡尔相乘.一般来说是够用的. 但其实多项式乘法算法还有很多更高效的. #include <iostream> #include <vector> #include <cstring> #include <cs

  • C++实现大数乘法算法代码

    C++实现大数乘法算法代码 复制代码 代码如下: //大数乘法算法 #include<iostream> #include<string> #include<cstring> using namespace std; int main() {     string num1,num2;     cin >> num1 >> num2;     //cout << num1.size() << " " &

  • C语言实现大整数加减运算详解

    前言 我们知道,在数学中,数值的大小是没有上限的,但是在计算机中,由于字长的限制,计算机所能表示的范围是有限的,当我们对比较小的数进行运算时,如:1234+5678,这样的数值并没有超出计算机的表示范围,所以可以运算.但是当我们在实际的应用中进行大量的数据处理时,会发现参与运算的数往往超过计算机的基本数据类型的表示范围,比如说,在天文学上,如果一个星球距离我们为100万光年,那么我们将其化简为公里,或者是米的时候,我们会发现这是一个很大的数.这样计算机将无法对其进行直接计算. 可能我们认为实际应

  • C++实现大整数乘法（字符串乘法）

    本文实例为大家分享了C++实现大整数乘法的具体代码,供大家参考,具体内容如下 #include<iostream> #include<algorithm> #include<string> using namespace std; string add(string a,string b) { if(a.length()==0) return b; if(b.length()==0) return a; a.length()<b.length()?a.swap(b

  • Python 实现大整数乘法算法的示例代码

    我们平时接触的长乘法,按位相乘,是一种时间复杂度为 O(n ^ 2) 的算法.今天,我们来介绍一种时间复杂度为 O (n ^ log 3) 的大整数乘法(log 表示以 2 为底的对数). 介绍原理 karatsuba 算法要求乘数与被乘数要满足以下几个条件,第一,乘数与被乘数的位数相同:第二,乘数与被乘数的位数应为  2 次幂,即为 2 ^ 2,  2 ^ 3, 2 ^ 4, 2 ^ n 等数值. 下面我们先来看几个简单的例子,并以此来了解 karatsuba 算法的使用方法. 两位数相乘 我

  • python 实现两个字符串乘法小练习

    python 实现两个字符串乘法小练习

    两个字符串相乘,基本思路是num1依次乘以num2各个数位上的数字,再将其累加,如下图所示: 需要注意的是,对于高位的乘积,需要在后面补0,0的个数和num2的数位有关系,十位补1个0,百位补2个0,假设num2的长度为n,从左到右对其数位编号为0.1.2...i,总结规律为:补0的个数=n-1-i. 以下是具体代码: #两个字符串相乘 #基本思路是num1依次乘以num2各个数位上的数字,再将其累加   from add_strings import add_strings1 # add_st

  • python里大整数相乘相关技巧指南

    问题 大整数相乘 思路说明 对于大整数计算,一般都要用某种方法转化,否则会溢出.但是python无此担忧了. Python支持"无限精度"的整数,一般情况下不用考虑整数溢出的问题,而且Python Int类型与任意精度的Long整数类可以无缝转换,超过Int 范围的情况都将转换成Long类型. 例如: >>> 2899887676637907866*1788778992788348277389943 5187258157415700236034169791337062

  • C/C++高精度运算(大整数运算)详细讲解

    目录 前言 什么是大整数 大整数的表示 大整数的运算 1.高精度加法 2.高精度减法 3.高精度乘以低精度 4.高精度除以低精度 大整数的表示 补充:使用示例 总结 前言 高精度的运算在算法题尤为常见,在处理一些大型数据的项目中也需要用到.虽然Boost库中有处理高精度问题的模板,但是标准库中并没有.为了方便学习,本文提供了高精度运算的模板,供大家参考. 什么是大整数 众所周知,最大的整型long long的范围是[-9223372036854775808~9223372036854775807

  • 对Python中小整数对象池和大整数对象池的使用详解

    1. 小整数对象池 整数在程序中的使用非常广泛,Python为了优化速度,使用了小整数对象池, 避免为整数频繁申请和销毁内存空间. Python 对小整数的定义是 [-5, 256] 这些整数对象是提前建立好的,不会被垃圾回收.在一个 Python 的程序中,无论这个整数处于LEGB中的哪个位置, 所有位于这个范围内的整数使用的都是同一个对象.同理,单个字母也是这样的. In [1]: a=-5 In [2]: b=-5 In [3]: a is b Out[3]: True In [4]: a

  • 浅谈JavaScript中小数和大整数的精度丢失

    先来看两个问题: 0.1 + 0.2 == 0.3; // false 9999999999999999 == 10000000000000000; // true 第一个问题是小数的精度问题,在业界不少博客里已有讨论.第二个问题,去年公司有个系统的数据库在做数据订正时,发现有部分数据重复的诡异现象.本文将从规范出发,对上面的问题做个小结. 最大整数 JavaScript 中的数字是用 IEEE 754 双精度 64 位浮点数 来存储的,其格式为: s x m x 2^e s 是符号位,表示正负

  • Java整数和字符串相互转化实例详解

    这篇文章主要介绍了Java整数和字符串相互转化实例详解,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友可以参考下 1.把int转化为String 以下三种方式把整形地i转化为字符串s,当然把Double.Float.Long转化为字符串操作一样. 1.String s=""+i; 2.String s=Integer.toString(i); 3.String s=String.valueOf(i); 2.把String转化为int型. 1.in

随机推荐