大整数加减运算的C语言实现

1、大整数加减运算的 C 语言实现一 . 问题提出培训老师给出一个题目：用C 语言实现一个大整数计算器。初步要求支持大整数的加、减运算，例如 8888888888888+1112=8888888890000 或1000000000000-999999999999=1C 语言中，整型变量所能存储的最宽数据为 0xFFFF FFFF ，对应的无符号数为 4294967295 ，即无法保存超过 10 位的整数。 注意， 此处10 位指数学中的 10 个数字， 并非计算机科学中的 10 比特。浮 点类型 double 虽然可以存储更多位数的整数，但一方面常 数字面量宽度受编译器限制，另一方面通过浮点方式处

2、理整 数精度较低。例如： double a = 1377083362513770833626.0, b=1585054852315850548524.0; printf(res = %.0fn, a+b); 输出为 res = 2962138214829621510144 ，而正确值应为 2962138214829621382150 。既然基本数据类型无法表示大 整数，那么只能自己设计存储方式来实现大整数的表示和运 算。通常，输入的大整数为字符串形式。因此，常见的思路 是将大整数字符串转化为数组，再用数组模拟大整数的运算。 具体而言，先将字符串中的数字字符顺序存入一个较大的整 型数组，其元素代

3、表整数的某一位或某几位(如万进制 )；然后根据运算规则操作数组元素，以模拟整数运算；最后，将数组元素顺序输出。数组方式操作方便，实现简单，缺点是 空间利用率和执行效率不高。也可直接操作大整数字符串， 从字符串末尾逆向计算。本文实现就采用这种方式。二 . 代 码实现首先，给出几个宏定义和运算结构： #include#include#include#define ADD_THRES (sizeof(4294967295)-2) / 两个 9 位整数相加不会溢出 #define MUL_THRES (sizeof(65535)-2) / 两个 4 位整数相 乘不会溢出 #define OTH_THR

4、ES (sizeof(4294967295)-1) /两个 10 位整数相减或相除不会溢出 typedef struct char *leftVal; char *rightVal; char operator;MATH_OPER;基于上述定义，以下将依次给出运算代码的实现。加法运算主要 关注相加过程中的进位问题： void Addition(char *leftVal, char *rightVal, char *resBuf, unsigned int resbufLen) unsigned int leftLen = strlen(leftVal); unsigned int right

5、Len = strlen(rightVal); unsigned char isLeftLonger = (leftLen=rightLen) ? 1 : 0; unsigned int longLen = isLeftLonger ? leftLen : rightLen; if(resbufLen /possible carry + string terminator fprintf(stderr, Not enough space for result(cur:%u)!n, resbufLen); return; char *longAddend = isLeftLonger ? lef

6、tVal : rightVal; char *shortAddend = isLeftLonger ? rightVal : leftVal; unsigned int diffLen = isLeftLonger ? (leftLen-rightLen) :(rightLen-leftLen); /a carry might be generated from adding the most significant digit if(leftLen = rightLen) & (leftVal0-0+rightVal0-0 = 9) resBuf += 1; unsigned int car

7、ry = 0; int i = longLen-1; for(; i = 0; i-) unsigned int leftAddend = longAddendi - 0; unsigned int rightAddend = (i0 : shortAddendi-diffLen-0; unsigned int digitSum = leftAddend + rightAddend + carry; resBufi = digitSum % 10 + 0; carry = (digitSum = 10) ? 1 : 0; if(carry = 1) resBuf -= 1; resBuf0 =

8、 1; else if(leftVal0-0+rightVal0-0 = 9) resBuf -= 1; resBuf0 = ; /fail to generate a carry 注意第 3336 行的处理，当 最高位未按期望产生进位时， 原来为 0 的 resBuf0 被置为空 格字符，否则将无法输出运算结果。当然，也可将 resBuf 整体前移一个元素。减法运算相对复杂，需要根据被减数和 减数的大小调整运算顺序。若被减数小于减数 (11-111 或 110-111) ，则交换被减数和减数后再做正常的减法运算， 并 且结果需添加负号前缀。此外，还需关注借位问题。 void Subtract

9、ion(char *leftVal, char *rightVal, char *resBuf, unsigned int resbufLen) int cmpVal = strcmp(leftVal, rightVal); if(!cmpVal) resBuf0 = 0; return; unsigned int leftLen = strlen(leftVal); unsigned int rightLen = strlen(rightVal); unsigned char isLeftLonger = 0; if(leftLen rightLen) | /100-10 (leftLen

10、= rightLen & cmpVal 0) /100-101 isLeftLonger = 1; unsigned int longLen = isLeftLonger ? leftLen : rightLen; if(resbufLen /string terminator fprintf(stderr, Not enough space for result(cur:%u)!n, resbufLen); return; char *minuend = isLeftLonger ? leftVal : rightVal; char *subtrahend = isLeftLonger ?

11、rightVal : leftVal; unsigned int diffLen = isLeftLonger ? (leftLen-rightLen) : (rightLen-leftLen); /a borrow will be generated from subtracting the most significant digit if(!isLeftLonger) resBuf0 = -; resBuf += 1; unsigned int borrow = 0; int i = longLen-1; for(; i = 0; i-) unsigned int expanSubtra

12、hend = (i0 : subtrahendi-diffLen; int digitDif = minuendi - expanSubtrahend - borrow; borrow = (digitDif 0) ? 1 : 0; resBufi = digitDif + borrow*10 + 0; /printf(%dDif=%d=%c-%c-%d - %cn, i, digitDif, minuendi, expanSubtrahend, borrow, resBufi); /strip leading 0 characters int iSrc = 0, iDst = 0, isSt

13、ripped = 0; while(resBufiSrc !=0) if(isStripped) resBufiDst = resBufiSrc; iSrc+; iDst+; else if(resBufiSrc != 0) resBufiDst = resBufiSrc; iSrc+; iDst+; isStripped = 1; else iSrc+; resBufiDst = 0;对于 Addition() 和Subtraction() 函数，设计测试用例如下： #include#define ASSERT_ADD(_add1, _add2, _sum) do char resBuf10

14、0 = 0; Addition(_add1, _add2, resBuf, sizeof(resBuf); assert(!strcmp(resBuf, _sum); while(0)#define ASSERT_SUB(_minu, _subt, _dif) do char resBuf100 = 0; Subtraction(_minu, _subt, resBuf, sizeof(resBuf); assert(!strcmp(resBuf, _dif); while(0)void VerifyOperation(void) ASSERT_ADD(22, 1686486458, 1686

15、486480); 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, 8

16、000000000000, 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, -80

17、55); ASSERT_SUB(1000000000000, 999999999999, 1); 考虑到语言内置的运算效率应该更高，因此在不可能产 生溢出时尽量选用内置运算。 CalcOperation() 函数便采用这 一思路： void CalcOperation(MATH_OPER *mathOper, char *resBuf, unsigned int resbufLen) unsigned int leftLen = strlen(mathOper-leftVal); unsigned int rightLen = strlen(mathOper-rightVal); switch

18、(mathOper-operator) case +: if(leftLen snprintf(resBuf, resbufLen, %d, atoi(mathOper-leftVal) + atoi(mathOper-rightVal); else Addition(mathOper-leftVal, mathOper-rightVal, resBuf, resbufLen); break; case -: if(leftLen snprintf(resBuf, resbufLen, %d, atoi(mathOper-leftVal) - atoi(mathOper-rightVal);

19、else Subtraction(mathOper-leftVal, mathOper-rightVal, resBuf, resbufLen); break; case *: if(leftLen snprintf(resBuf, resbufLen, %d, atoi(mathOper-leftVal) * atoi(mathOper-rightVal); else break; /Multiplication: product = multiplier * multiplicand break; case /: if(leftLen snprintf(resBuf, resbufLen,

20、 %d, atoi(mathOper-leftVal) / atoi(mathOper-rightVal); else break; /Division: quotient= dividend / divisor break; default: break; return;注意，大整数的乘法和除法运算尚未实现，因此相应代码分支直接返 回。最后， 完成入口函数： int main(void) VerifyOperation(); char leftVal100 = 0, rightVal100 = 0, operator=+; char resBuf1000 = 0; /As you see,

21、basically any key can quit:) printf(Enter math expression(press q to quit): ); while(scanf( %0-9 %+-*/ %0-9, leftVal, &operator, rightVal) = 3) MATH_OPER mathOper = leftVal, rightVal, operator; memset(resBuf, 0, sizeof(resBuf); CalcOperation(&mathOper, resBuf, sizeof(resBuf); printf(%s %c %s = %sn, leftVal, operator, rightVal, resBuf); printf(Enter math expression(press q to q