C语言实现大整数加减运算详解
前言
我们知道,在数学中,数值的大小是没有上限的,但是在计算机中,由于字长的限制,计算机所能表示的范围是有限的,当我们对比较小的数进行运算时,如:1234+5678,这样的数值并没有超出计算机的表示范围,所以可以运算。但是当我们在实际的应用中进行大量的数据处理时,会发现参与运算的数往往超过计算机的基本数据类型的表示范围,比如说,在天文学上,如果一个星球距离我们为100万光年,那么我们将其化简为公里,或者是米的时候,我们会发现这是一个很大的数。这样计算机将无法对其进行直接计算。
可能我们认为实际应用中的大数也不过就是几百位而已,实际上,在某些领域里,甚至可能出现几百万位的数据进行运算,这是我们很难想象的。如果没有计算机,那么计算效率可想而知。
由于编程语言提供的基本数值数据类型表示的数值范围有限,不能满足较大规模的高精度数值计算,因此需要利用其他方法实现高精度数值的计算,于是产生了大数运算。本项目实现了大数运算的加、减运算。
一.问题提出
用C语言实现一个大整数计算器。初步要求支持大整数的加、减运算,例如8888888888888+1112=8888888890000或1000000000000-999999999999=1。
C语言中,整型变量所能存储的最宽数据为0xFFFFFFFF,对应的无符号数为4294967295,即无法保存超过10位的整数。注意,此处"10位"指数学中的10个数字,并非计算机科学中的10比特。浮点类型double虽然可以存储更多位数的整数,但一方面常数字面量宽度受编译器限制,另一方面通过浮点方式处理整数精度较低。例如:
doublea=1377083362513770833626.0,b=1585054852315850548524.0; printf("res=%.0f\n",a+b);
输出为res=2962138214829621510144,而正确值应为2962138214829621382150。
既然基本数据类型无法表示大整数,那么只能自己设计存储方式来实现大整数的表示和运算。通常,输入的大整数为字符串形式。因此,常见的思路是将大整数字符串转化为数组,再用数组模拟大整数的运算。具体而言,先将字符串中的数字字符顺序存入一个较大的整型数组,其元素代表整数的某一位或某几位(如万进制);然后根据运算规则操作数组元素,以模拟整数运算;最后,将数组元素顺序输出。
数组方式操作方便,实现简单,缺点是空间利用率和执行效率不高。也可直接操作大整数字符串,从字符串末尾逆向计算。本文实现就采用这种方式。
二.代码实现
首先,给出几个宏定义和运算结构:
#include<stdio.h> #include<stdlib.h> #include<string.h> #defineADD_THRES(sizeof("4294967295")-2)//两个9位整数相加不会溢出 #defineMUL_THRES(sizeof("65535")-2)//两个4位整数相乘不会溢出 #defineOTH_THRES(sizeof("4294967295")-1)//两个10位整数相减或相除不会溢出 typedefstruct{ char*leftVal; char*rightVal; charoperator; }MATH_OPER;
基于上述定义,以下将依次给出运算代码的实现。
加法运算主要关注相加过程中的进位问题:
voidAddition(char*leftVal,char*rightVal, char*resBuf,unsignedintresbufLen){ unsignedintleftLen=strlen(leftVal); unsignedintrightLen=strlen(rightVal); unsignedcharisLeftLonger=(leftLen>=rightLen)?1:0; unsignedintlongLen=isLeftLonger?leftLen:rightLen; if(resbufLen<longLen){//possiblecarry+stringterminator fprintf(stderr,"Notenoughspaceforresult(cur:%u)!\n",resbufLen); return; } char*longAddend=isLeftLonger?leftVal:rightVal; char*shortAddend=isLeftLonger?rightVal:leftVal; unsignedintdiffLen=isLeftLonger?(leftLen-rightLen):(rightLen-leftLen); //acarrymightbegeneratedfromaddingthemostsignificantdigit if((leftLen==rightLen)&&(leftVal[0]-'0'+rightVal[0]-'0'>=9)) resBuf+=1; unsignedintcarry=0; inti=longLen-1; for(;i>=0;i--){ unsignedintleftAddend=longAddend[i]-'0'; unsignedintrightAddend=(i<diffLen)?0:shortAddend[i-diffLen]-'0'; unsignedintdigitSum=leftAddend+rightAddend+carry; resBuf[i]=digitSum%10+'0'; carry=(digitSum>=10)?1:0; } if(carry==1){ resBuf-=1; resBuf[0]='1'; } elseif(leftVal[0]-'0'+rightVal[0]-'0'==9){ resBuf-=1; resBuf[0]='';//failtogenerateacarry } }
注意第33~36行的处理,当最高位未按期望产生进位时,原来为0的resBuf[0]被置为空格字符,否则将无法输出运算结果。当然,也可将resBuf整体前移一个元素。
减法运算相对复杂,需要根据被减数和减数的大小调整运算顺序。若被减数小于减数("11-111"或"110-111"),则交换被减数和减数后再做正常的减法运算,并且结果需添加负号前缀。此外,还需关注借位问题。
voidSubtraction(char*leftVal,char*rightVal, char*resBuf,unsignedintresbufLen){ intcmpVal=strcmp(leftVal,rightVal); if(!cmpVal){ resBuf[0]='0'; return; } unsignedintleftLen=strlen(leftVal); unsignedintrightLen=strlen(rightVal); unsignedcharisLeftLonger=0; if((leftLen>rightLen)||//100-10 (leftLen==rightLen&&cmpVal>0))//100-101 isLeftLonger=1; unsignedintlongLen=isLeftLonger?leftLen:rightLen; if(resbufLen<=longLen){//stringterminator fprintf(stderr,"Notenoughspaceforresult(cur:%u)!\n",resbufLen); return; } char*minuend=isLeftLonger?leftVal:rightVal; char*subtrahend=isLeftLonger?rightVal:leftVal; unsignedintdiffLen=isLeftLonger?(leftLen-rightLen):(rightLen-leftLen); //aborrowwillbegeneratedfromsubtractingthemostsignificantdigit if(!isLeftLonger){ resBuf[0]='-'; resBuf+=1; } unsignedintborrow=0; inti=longLen-1; for(;i>=0;i--) { unsignedintexpanSubtrahend=(i<diffLen)?'0':subtrahend[i-diffLen]; intdigitDif=minuend[i]-expanSubtrahend-borrow; borrow=(digitDif<0)?1:0; resBuf[i]=digitDif+borrow*10+'0'; //printf("[%d]Dif=%d=%c-%c-%d->%c\n",i,digitDif,minuend[i],expanSubtrahend,borrow,resBuf[i]); } //stripleading'0'characters intiSrc=0,iDst=0,isStripped=0; while(resBuf[iSrc]!='\0'){ if(isStripped){ resBuf[iDst]=resBuf[iSrc]; iSrc++;iDst++; } elseif(resBuf[iSrc]!='0'){ resBuf[iDst]=resBuf[iSrc]; iSrc++;iDst++; isStripped=1; } else iSrc++; } resBuf[iDst]='\0'; }
对于Addition()和Subtraction()函数,设计测试用例如下:
#include<assert.h> #defineASSERT_ADD(_add1,_add2,_sum)do{\ charresBuf[100]={0};\ Addition(_add1,_add2,resBuf,sizeof(resBuf));\ assert(!strcmp(resBuf,_sum));\ }while(0) #defineASSERT_SUB(_minu,_subt,_dif)do{\ charresBuf[100]={0};\ Subtraction(_minu,_subt,resBuf,sizeof(resBuf));\ assert(!strcmp(resBuf,_dif));\ }while(0) voidVerifyOperation(void){ ASSERT_ADD("22","1686486458","1686486480"); ASSERT_ADD("8888888888888","1112","8888888890000"); ASSERT_ADD("1234567890123","1","1234567890124"); ASSERT_ADD("1234567890123","3333333333333","4567901223456"); ASSERT_ADD("1234567890123","9000000000000","10234567890123"); ASSERT_ADD("1234567890123","8867901223000","10102469113123"); ASSERT_ADD("1234567890123","8000000000000","9234567890123"); ASSERT_ADD("1377083362513770833626","1585054852315850548524","2962138214829621382150"); ASSERT_SUB("10012345678890","1","10012345678889"); ASSERT_SUB("1","10012345678890","-10012345678889"); ASSERT_SUB("10012345678890","10012345678891","-1"); ASSERT_SUB("10012345678890","10012345686945","-8055"); ASSERT_SUB("1000000000000","999999999999","1"); }
考虑到语言内置的运算效率应该更高,因此在不可能产生溢出时尽量选用内置运算。CalcOperation()函数便采用这一思路:
voidCalcOperation(MATH_OPER*mathOper,char*resBuf,unsignedintresbufLen){ unsignedintleftLen=strlen(mathOper->leftVal); unsignedintrightLen=strlen(mathOper->rightVal); switch(mathOper->operator){ case'+': if(leftLen<=ADD_THRES&&rightLen<=ADD_THRES) snprintf(resBuf,resbufLen,"%d", atoi(mathOper->leftVal)+atoi(mathOper->rightVal)); else Addition(mathOper->leftVal,mathOper->rightVal,resBuf,resbufLen); break; case'-': if(leftLen<=OTH_THRES&&rightLen<=OTH_THRES) snprintf(resBuf,resbufLen,"%d", atoi(mathOper->leftVal)-atoi(mathOper->rightVal)); else Subtraction(mathOper->leftVal,mathOper->rightVal,resBuf,resbufLen); break; case'*': if(leftLen<=MUL_THRES&&rightLen<=MUL_THRES) snprintf(resBuf,resbufLen,"%d", atoi(mathOper->leftVal)*atoi(mathOper->rightVal)); else break;//Multiplication:product=multiplier*multiplicand break; case'/': if(leftLen<=OTH_THRES&&rightLen<=OTH_THRES) snprintf(resBuf,resbufLen,"%d", atoi(mathOper->leftVal)/atoi(mathOper->rightVal)); else break;//Division:quotient=dividend/divisor break; default: break; } return; }
注意,大整数的乘法和除法运算尚未实现,因此相应代码分支直接返回。
最后,完成入口函数:
intmain(void){ VerifyOperation(); charleftVal[100]={0},rightVal[100]={0},operator='+'; charresBuf[1000]={0}; //Asyousee,basicallyanykeycanquit:) printf("Entermathexpression(pressqtoquit):"); while(scanf("%[0-9]%[+-*/]%[0-9]",leftVal,&operator,rightVal)==3){ MATH_OPERmathOper={leftVal,rightVal,operator}; memset(resBuf,0,sizeof(resBuf)); CalcOperation(&mathOper,resBuf,sizeof(resBuf)); printf("%s%c%s=%s\n",leftVal,operator,rightVal,resBuf); printf("Entermathexpression(pressqtoquit):"); } return0; }
上述代码中,scanf()函数的格式化字符串风格类似正则表达式。其详细介绍参见《sscanf的字符串格式化用法》一文。
三.效果验证
将上节代码存为BigIntOper.c文件。测试结果如下:
[wangxiaoyuan_@localhost~]$gcc-Wall-oBigIntOperBigIntOper.c [wangxiaoyuan_@localhost~]$./BigIntOper Entermathexpression(pressqtoquit):100+901 100+901=1001 Entermathexpression(pressqtoquit):100-9 100-9=91 Entermathexpression(pressqtoquit):1234567890123+8867901223000 1234567890123+8867901223000=10102469113123 Entermathexpression(pressqtoquit):1377083362513770833626-1585054852315850548524 1377083362513770833626-1585054852315850548524=-207971489802079714898 Entermathexpression(pressqtoquit):q [wangxiaoyuan_@localhost~]$
通过内部测试用例和外部人工校验,可知运算结果正确无误。
总结
以上就是C语言实现大整数加减运算的全部内容,大家都学会了吗?希望本文的内容对大家学习C语言能有所帮助。