两个大数相乘

计算机一般能处理的数据有限，如int为32位二进制数，double为64位二进制数，当有两个个200位的数字，怎么计算其结果呢，

这个可以用数组来计算，模仿小学时计算数学乘法一样，数组将两个数字的每一位都存为数字，然后逐位相乘，相加来得出结果。

如：

? ? ? ? ? ?1 2 3

? ? ? ? x

? ? ? ? ? ?1 2 3

————————

? ? ? ? ? ? ? 3 6 9

? ? ? ? ? ?2 4 6

? ? ? ? 1 2 3

————————

? ? ? ? 1 5 1 2 9

说明一下：这个乘法每次运算都是把结果存起来，并且有规律的，第0位与第0位乘得第（0+0）位，第1位与第0为乘得第（1+0）位，

依次类推

当然计算机计算也可以这样，但数字的位置应该调换一下，低位在前高位在后，这样算出来的结果在逆序输出即可，原因是：这样

索引的计算比较方便

代码如下：

#include "stdio.h"
#include "iostream"
#include "cstring"
#define N 200
#define N2 2*N
using namespace std;

int main(){
	//存储两个数字字符串
	char strn1[N],strn2[N];
	// 将两个字符串转换为数字存储
	int num1[N],num2[N];
	//存储结果
	int result[N2];

	cin>>strn1>>strn2;

	int i,j =0;
	int len1 = strlen(strn1);
	int len2 = strlen(strn2);
	memset(num1,sizeof(num1));
	memset(num2,sizeof(num2));

	//将字符串转换为数字，并逆序
	for(i = len1 - 1;i>=0;i--){
		num1[j++] = strn1[i] - '0';
	}

	j = 0;

	for(i = len2 - 1;i>=0;i--){
		num2[j++] = strn2[i] - '0';
	}

	memset(result,sizeof(result));
	//用第一个数字的每一位乘以数字2的每一位，乘得的结果存入相应的位置
	//这个位置的由来：
	//两个数字都逆序了，那么最小位都在0坐标，而结果，数字1第0与数字2第0为的乘积
	//存储在结果的第零位，相应的可以数字第1为和数字2的第三为乘积应存储到结果的第
	//1+2位，依次类推
	for(i = 0;i<len1;i++){
		for(j = 0;j < len2;j++){
			result[j + i] += num1[i] * num2[j]; 
		}
	}

	//处理结果，将结果中大于9的进位，并存储为单一数字
	for(i = 0;i<400;i++){
	
		result[i + 1]  += result[i] / 10;//向高位进位result[i] / 10
		result[i] = result[i] % 10;      //进位后，原本位应为余数
	}
	//通过逆序输出，得出结果
	//注意这里从后面输出，可能是为0,所以设置一个标记，当第一次
	//遇见不是0时，其余的所有的数字包括0都是有效的
	int flag = 0;
	for(i = 400 - 1;i>=0;i--){
		if(flag){
			printf("%d",result[i]);

		} else if(result[i]){
			flag = 1;
			printf("%d",result[i]);
		}
	}
	printf("n");
	return 0;
}

实现如下：

/*
	Filename:twoBigMultiByStirng.cpp
	Author: xiaobing
	E-mail: xiaobingzhang29@gmail.com
	Date: 2013-08-23
*/
#include<iostream>
#include<string>
#include<algorithm>
#include<cstdlib>
#include<cstdio>
using namespace std;
string trim(string str){
	string buff(str);
	char space = ' ';
	str.assign(buff.begin() + buff.find_first_not_of(space),buff.begin() + buff.find_last_not_of(space) + 1)
	return str;
}
int main(){

	//输入两个随意长的字符串
	string str1,str2;
	cin>>str1>>str2;

	//去掉首位空格
	str1 = trim(str1);
	str2 = trim(str2);
	//获取每个字符串的长度
	int len1 = str1.length();
	int len2 = str2.length();
	int total = len1 + len2;

	//将字符串逆序
	string num1(str1.rbegin(),str1.rend());
	string num2(str2.rbegin(),str2.rend());

	cout<<"Reversed string one: "<<num1<<endl;
	cout<<"Reversed string two: "<<num2<<endl;

	//动态分配结果的空间字符串，一个n位数乘以m位数最多为n+m位数
	char *result;
	result = (char*)malloc(len1 + len2);

	//初始化结果全为'0'
	int i,j;
	for(i = 0;i < len1 + len2;i++){
		result[i] = '0';
	}

	//将第一个数字的每一位乘以第二个数字的每一位
	for(i = 0;i < len1;i++){
	
		for(j = 0;j < len2;j++){
			//结果存储位置
			int pos = i + j;	
			//第一个个数的第i位和第二个数的第j位乘积再加上pos位置的真值
			int tmp = (num1[i] - '0') * (num2[j] - '0') + (result[i + j] - '0'); 
			//结果为真值对10求余数
			result[i + j] = tmp % 10 + '0';
			//产生的进位
			int carry = tmp / 10;

			//当进位大于0,则更新下一位，一直更新，直到进位为0
			while(carry > 0){
				//下一个位置的数真值加上进位得到tmp
				tmp = result[pos + 1] - '0' + carry;
				//下一个位置等于tmp对10求余数
				result[pos + 1] = tmp % 10 + '0';
				//计算进位
				carry = tmp / 10;
				//移动位置
				pos++;
			}		

		}
	}

	cout<<"乘积为："<<endl;
	//输出结果，由于是逆序存储，所以从后面往前面输出
	//输出时，当遇见大于0的数开始输出，以后的数不管
	//是0或非0都有效
	int flag = 0;
	for(i = len1 + len2 - 1;i >= 0;i--){
		if(flag == 1){
			cout<<result[i];
		} else if (result[i] != '0'){
			flag = 1;
			cout<<result[i];
		}
	}
	cout<<endl;

	free(result);
    return 0;
}