simu_computer_mul_str.c

2个1000位大整数相乘

//模拟计算机的运算，先把10进制转换成2进制，然后移位相加，最后转变回10进制。
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

//char *str_a = "111111111111111";
char *str_a = "3";
//char *str_b = "123456789012345";
char *str_b = "1025";

//先把10进制转换成2进制
int tran_bin (char *str, char **res, int *aim_len)
{
	if ((str == NULL) || (res == NULL) || (aim_len == NULL))
	{
		printf ("%s.%d\n", __FILE__, __LINE__);
		exit (1);
	}
	int str_len = strlen (str);
	char *tmp = (char *)malloc (str_len + 1);
	memcpy (tmp, str, str_len);
	tmp[str_len] = '\0';

	int res_len = str_len * 4  + 4;
	*res = (char *)malloc (res_len + 1);
	memset (*res, '0', res_len + 1);
	(*res)[res_len] = '\0';

	int dig = 0;
	int len = str_len;
	int value;
	int res_index = 0;
	int i;
	while (len != 0)
	{
		dig = 0;
		for (i = str_len - len; i < str_len; i++)
		{
			value = tmp[i] - '0' + dig * 10;
			tmp[i] = value / 2 + '0';
			dig = value % 2;
		}
		(*res)[res_index++] = dig + '0';

		if (tmp[str_len - len] == '0')
			len--;
	}
	*aim_len = res_index;
	for (i = 0; i <= (res_index - 1) / 2; i++)
	{
		char ch = (*res)[i];
		(*res)[i] = (*res)[res_index - 1 - i];
		(*res)[res_index - 1 - i] = ch;
	}

	for (i =0; i < 80; i++)
		printf ("%d", i % 10);
	printf ("\n");
	printf ("res= %s\n", *res);
	printf ("res_index= %d\n", res_index);

	return 0;
}
//移位相加
int mul_bin (char **dst, int dst_len,  char **src, int src_len, char **aim)
{
	if ((dst == NULL) || (src == NULL) || (aim == NULL))
	{
		printf ("%s.%d\n", __FILE__, __LINE__);
		exit (1);
	}
	int res_len = ((dst_len + src_len + 1) / 4) * 4 + 4;
	char *res = (char *)malloc (res_len + 1);
	memset (res, '0', res_len);
	res[res_len] = '\0';

	int i;
	int j;
	int k;
	for (i = 0; i < src_len; i++)
	{
		if ((*src)[i] == '1')
		{
			int acc = 0;
			int value;
			for (j = dst_len - 1, k = res_len - (src_len - i); j >= 0; j--, k--)
			{
				value = res[k] - '0' + (*dst)[j] - '0' + acc;
				res[k] = value % 2 + '0';
				acc = value / 2;		
			}
			while (acc == 1)
			{
				value = res[k] - '0' + acc;
				res[k] = value % 2 + '0';
				acc = value / 2;
				k--;
			}
		}
	}
	*aim = res;
	printf ("%s\n", res);
	printf ("aim_len= %d\n", res_len);
	
	return 0;
}
//转变回10进制
int tran_dec (char *aim, char **dec_res)
{
	int len = strlen (aim);
	*dec_res = (char *)malloc (len + 1);
	if (*dec_res == NULL)
	{
		printf ("%s.%d\n", __FILE__, __LINE__);
		exit (1);
	}
	memset (*dec_res, '0', len);
	(*dec_res)[len] = '\0';
	
	int stand_step = 0;
	char *stand_exp = (char *)malloc (len + 1);
	if (stand_exp == NULL)
	{
		printf ("%s.%d\n", __FILE__, __LINE__);
		exit (1);
	}
	memset (stand_exp, '0', len);
	stand_exp[len] = '\0';
	stand_exp[len - 1] = '1';

	int i;
	int j;
	int acc;
	int value;
	for (i = len - 1; i >= 0; i--)
	{
		if (aim[i] == '1')
		{
			acc = 0;
			for (j = len - 1; j >= 0; j--)
			{
				value = (*dec_res)[j] - '0' + stand_exp[j] - '0' + acc;
				(*dec_res)[j] = value % 10 + '0';
				acc = value / 10;
			}	
		}
		// 2 multiple of stand_exp
		acc = 0;
		for (j = len - 1; j >= 0; j--)
		{
			value = (stand_exp[j] - '0') * 2 + acc;
			stand_exp[j] = value % 10 + '0';
		   	acc = value / 10;
		}
	}
	
	return 0;
}

int main (int argc, char **argv)
{
	char *res_a;
	char *res_b;
	int len_a;
	int len_b;
	//tran_bin (str_a, &res_a, &len_a);
	tran_bin (argv[1], &res_a, &len_a);
	//tran_bin (str_b, &res_b, &len_b);
	tran_bin (argv[2], &res_b, &len_b);
	char *aim;
	mul_bin (&res_a, len_a, &res_b, len_b, &aim);
	char *dec_res;
	tran_dec (aim, &dec_res);
	int i = 0;
	while (dec_res[i] == '0')
		i++;
	printf ("%s\n", dec_res + i);
	printf ("len= %d\n", strlen (dec_res + i));
	
	return 0;
}