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语言能有所帮助。