大数的加减法、乘除法 code

大数：超过计算机默认可表示的最长值

这里的实现未考虑小数，大数可以含正负符号，可含前导零（如+000001111、-0000000）

大数用字符串表示

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

bool IsDigital(const char *string)  
{  
	if (*string == '-' || *string == '+')
		string++;
	
		while(*string >= '0' && *string <= '9')
		string++;
	
	return *string ? false : true;
}  

/**
 * brief 倒转字符串
 */
void StrAjust(char *string)  
{  
	int length = strlen(string);  
	int tmp;  
	for(int i = 0; i < length / 2; i++)  
	{  
		tmp = string[i];  
		string[i] = string[length - i - 1];  
		string[length - i - 1] = tmp;  
	}  
}
/**
 * brief 大数比较，通过值/结果参数ret返回比较结果
 */
int BignumCmp(const char *num1,const char *num2,int *ret)
{
	int len1,len2,len;
	const char *tmp1 = num1,*tmp2 = num2;
	
	if (!num1 || !num2)
		return -1;
	len1 = strlen(num1),len2 = strlen(num2);
	
	if (*num1 == '-' || *num1 == '+')
		tmp1++,len1--;
	
	if (*num2 == '-' || *num2 == '+')
		tmp2++,len2--;
	
	if (len1 > len2) {
		len1 = len1 - len2;
		len2 = 0;
	} 
	else {
		len2 = len2 - len1;
		len1 = 0;
	}
	
	*ret = 0;
	for (len = 0; len < len1; len++) {
		if (tmp1[len] != '0') {
			*ret = 1;
			break;
		}
	}
	
	for (len = 0; len < len2; len++) {
		if (tmp2[len] != '0') {
			*ret = -1;
			break;
		}
	}
	
	if (*ret == 0) {
		while (tmp1[len1] && tmp2[len2]) {
			if (tmp1[len1] != tmp2[len2]) {
				*ret = tmp1[len1] - tmp2[len2];
				break;
			}
			len1++,len2++;
		}
	}

	if (*num1 != '-') {
		if (*num2 == '-')
			*ret = *ret >= 0 ? *ret : 1;
	}
	else {
		if (*num2 == '-')
			*ret = 0 - *ret;
		else
			*ret = *ret <= 0 ? *ret : -1;
	}
	
	return 0;	
}

/**
 * brief 大数加/减法,可以带符号位'+'/'-',*/
char *BignumSum(const char *num1,const char *num2)
{
#define NUMM (3)
	int cmp,ret,flag,blen,slen,increment;
	const char *tmp1 = num1,*tmp2 = num2,*bigger,*smaller;
	char *res,*rp,sign;
	
	if (!num1 || !num2)
		return NULL;
	
	flag = 0;
	if ((*num1 == '-' && *num2 == '-') || (*num1 != '-' && *num2 != '-'))
		flag = 1;
		
	if (*num1 == '-' || *num1 == '+')
		tmp1 = num1 + 1;
	if (*num2 == '-' || *num2 == '+')
		tmp2 = num2 + 1;
		
	ret = BignumCmp(tmp1,tmp2,&cmp);
	if (ret)
		return NULL;
		
	if (!cmp && !flag) {
		res = (char *)malloc(NUMM);
		if (!res)
			return NULL;
		rp = res;
		*rp++ = '0';
		*rp = 0;
		return res;
	}
		
	if (cmp > 0){
		bigger = tmp1,sign = *num1;
		smaller = tmp2;
	} 
	else {
		bigger = tmp2,sign = *num2;
		smaller = tmp1;
	}
	blen = strlen(bigger);
	slen = strlen(smaller);
	
	// + NUMM： 包含结束符、符号位、可能的进位
	res = (char *)malloc(blen + NUMM);
	if (!res)
		return NULL;
	rp = res;
	if (sign == '-')
		*rp++ = '-';
	
	// 从个位开始往高位依次相加
	for (increment = 0; blen > 0;) {
		int tmp;
		char smallernum = slen > 0 ? smaller[--slen] - '0' : 0;
		if (flag) {
			tmp = bigger[--blen] - '0' + smallernum + increment;
			increment = tmp / 10;
		}
		else {
			tmp = bigger[--blen] - '0' - smallernum + increment;
			tmp = tmp < 0 ? (increment = -1,tmp + 10) : (increment = 0,tmp);
		}
		*rp++ = tmp % 10 + '0';
	}
	
	// 最高位进位
	if (increment)
		*rp++ = increment + '0';
	
	// 清除前缀零
	*rp = 0;
	while (*(--rp) == '0')
		*rp = 0;
	
	rp = res;
	if (sign == '-')
		rp = res + 1;
	StrAjust(rp);
	
	return res;
}

/**
 * brief 大数乘法,*/
char *BignumMulti(const char *num1,const char *num2)
{
	int increment,len1,len2;
	char *res,*rp;
	if (!num1 || !num2)
		return NULL;
	
	len1 = strlen(num1);
	len2 = strlen(num2);
	res = (char *)malloc(len1 + len2 + 1);
	if (!res)
		return NULL;
	memset(res,len1 + len2 + 1);
	rp = res;
	
	if ((*num1 == '-' && *num2 != '-') || (*num1 != '-' && *num2 == '-'))
		*rp++ = '-';
	
	if (*num1 == '-' || *num1 == '+') {
		num1++,len1--;
	}
	if (*num2 == '-' || *num2 == '+') {
		num2++,len2--;
	}
	
	// num1 乘数， num2 被乘数
	for (int i = len1 - 1; i >= 0; i--) {
		int j,num1tmp = num1[i] - '0';
		increment = 0;
		for (j = len2 - 1; j >= 0; j--) {
			int tmp1;
			char *tmp2; 
			tmp1 = num1tmp * (num2[j] - '0') + increment;
			tmp2 = rp + len1 - i + len2 - j - 2;
			tmp1 = *tmp2 + tmp1;
			*tmp2 = tmp1 % 10;
			increment = tmp1 / 10;
		}
		if (increment)
			*(rp + len1 - i + len2 - 1) = increment;	
	}
	rp = rp + len1 + len2 - 1;
	
	// 清除前导零
	while (*rp == 0)
		rp--;
	
	if (rp < res || (*res == '-' && rp == res)) {
		*res = '0';
		return res;
	}

	while (rp >= res && *rp != '-') {
		*rp = *rp + '0';
		rp--;
	}
	
	rp = res;
	if (*res == '-')
		rp = res + 1;
		
	StrAjust(rp);
	return res;
}

/**
 * brief 大数求相反数,*/
char *BignumMinus(const char*num)
{
	int len;
	char *res,*rp;
	const char *tmp;
	
	if (!num)
		return NULL;
	
	tmp = num;
	while (*tmp == '-' || *tmp == '+' || *tmp == '0')
		tmp++;
		
	len = strlen(tmp);
	
	res = (char *)malloc(len + 2);
	if (!res)
		return NULL;
	
	if (!len) {
		*res = '0';
		*(res + 1) = 0;
		return res;
	}
	
	rp = res;
	if (*num != '-') {
		*res = '-';
		rp++;
	}
		
	strcpy(rp,tmp);
	return res;
}

/**
 * brief 大数除法,*/
char *BignumDivi(const char *num1,const char *num2)
{
	int cmp,len;
	char *tmp,*res;
	char *tmp1,*tmp2;
	
	
	if (!num1 || !num2)
		return NULL;
	if (BignumCmp(num2,"0",&cmp) || !cmp)
		return NULL;
	
	for (tmp1 = (char *)num1; *tmp1 && (*tmp1 == '-' || *tmp1 == '+' || *tmp1 == '0'); tmp1++) ;
	for (tmp2 = (char *)num2; *tmp2 && (*tmp2 == '-' || *tmp2 == '+' || *tmp2 == '0'); tmp2++) ;
	
	len1 = strlen(tmp1),len2 = strlen(tmp2);

	res = (char *)malloc(2);
	if (!res)
		return NULL;
	memset(res,2);
	
	BignumCmp(tmp1,&cmp);
	if (cmp < 0) {
		*res = '0';
	}
	else if (cmp == 0) {
		*res = '1';
	}
	else {	
		tmp = (char *)malloc(len1 + 1);
		if (!tmp) {
			free(res);
			return NULL;
		}
		strncpy(tmp,len1 + 1);
		tmp2 = tmp;
		
		tmp = (char *)malloc(len1 + 1);
		if (!tmp) {
			free(res);
			free(tmp2);
			return NULL;
		}
		strncpy(tmp,tmp1,len1 + 1);
		tmp1 = tmp;
	
		len = len1 - len2;
		while (len >= 0) { // 被除数比除数多len个字符
			int start = 0,end = 9;
			char *rest,increment[2] = {0};
			
			memset(tmp2 + len2,'0',len);  // 补零
			tmp2[len2 + len] = 0;
			
			// 二分查找合适的除法结果
			while (start <= end) {
				int mid = (start + end) / 2;
				
				if (mid == start && start < end)
					mid++;
				increment[0] = mid + '0';
				
				rest = BignumMulti(tmp2,increment);
				
				if (start == end)
					break;
					
				BignumCmp(tmp1,rest,&cmp);
				if (cmp >= 0)
					start = mid;
				else
					end = mid - 1;
				free(rest);
			}
			
			tmp = BignumMinus(rest);
			free(rest),rest = tmp;
			tmp = BignumSum(tmp1,rest);
			free(tmp1),free(rest),tmp1 = tmp;
			
			increment[0] = start + '0';
			rest = BignumMulti(res,"10");
			free(res),res = rest;
			rest = BignumSum(res,increment);
			free(res),res = rest;
	
			len--;
		}
		free(tmp1);
		free(tmp2);
	}
	
	if ((*num1 == '-' && *num2 != '-') || (*num1 != '-' && *num2 == '-')) {
		tmp = BignumMinus(res);
		free(res),res = tmp;
	}
	
	return res;	
}


int main(int argc,char **argv)  
{ 
	bool ret1,ret2;
	char *multi,*sum,*divi;
	
	if(3 != argc)  
		return -1;   
	
	ret1 = IsDigital(argv[1]);  
	ret2 = IsDigital(argv[2]);  
	
	if(!ret1 || !ret2) {  
		printf("input errorn");  
		return -1;  
	}  
	sum= BignumSum(argv[1],argv[2]);  
	multi= BignumMulti(argv[1],argv[2]);
	divi = BignumDivi(argv[1],argv[2]);	

	printf("num1：%snnum2：%snsum：%snmulti：%sndivi: %sn",argv[1],argv[2],sum,multi,divi);
	
	free(sum);
	free(multi);
	free(divi);
	
	return 0;  
}