[关闭]
@cloverwang 2016-06-22T07:37:27.000000Z 字数 6924 阅读 2570

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

大整数加减 C

一. 问题提出

培训老师给出一个题目：用C语言实现一个大整数计算器。初步要求支持大整数的加、减运算，例如8888888888888+1112=8888888890000或1000000000000-999999999999=1。

C语言中，整型变量所能存储的最宽数据为0xFFFF FFFF，对应的无符号数为4294967295，即无法保存超过10位的整数。注意，此处"10位"指数学中的10个数字，并非计算机科学中的10比特。浮点类型double虽然可以存储更多位数的整数，但一方面常数字面量宽度受编译器限制，另一方面通过浮点方式处理整数精度较低。例如：

  1.     double a = 1377083362513770833626.0, b=1585054852315850548524.0;
  2.     printf("res = %.0f\n", a+b);

输出为res = 2962138214829621510144，而正确值应为2962138214829621382150。

既然基本数据类型无法表示大整数，那么只能自己设计存储方式来实现大整数的表示和运算。通常，输入的大整数为字符串形式。因此，常见的思路是将大整数字符串转化为数组，再用数组模拟大整数的运算。具体而言，先将字符串中的数字字符顺序存入一个较大的整型数组，其元素代表整数的某一位或某几位(如万进制)；然后根据运算规则操作数组元素，以模拟整数运算；最后，将数组元素顺序输出。

数组方式操作方便，实现简单，缺点是空间利用率和执行效率不高。也可直接操作大整数字符串，从字符串末尾逆向计算。本文实现就采用这种方式。

二. 代码实现

首先，给出几个宏定义和运算结构：

  1. #include<stdio.h>
  2. #include<stdlib.h>
  3. #include<string.h>
  5. #define ADD_THRES     (sizeof("4294967295")-2)  //两个9位整数相加不会溢出
  6. #define MUL_THRES     (sizeof("65535")-2)       //两个4位整数相乘不会溢出
  7. #define OTH_THRES     (sizeof("4294967295")-1)  //两个10位整数相减或相除不会溢出
  9. typedef struct{
  10.     char *leftVal;
  11.     char *rightVal;
  12.     char operator;
  13. }MATH_OPER;

基于上述定义，以下将依次给出运算代码的实现。

加法运算主要关注相加过程中的进位问题：

  1. void Addition(char *leftVal,  char *rightVal,
  2.               char *resBuf, unsigned int resbufLen) {
  3.     unsigned int leftLen = strlen(leftVal);
  4.     unsigned int rightLen = strlen(rightVal);
  6.     unsigned char isLeftLonger = (leftLen>=rightLen) ? 1 : 0;
  7.     unsigned int longLen = isLeftLonger ? leftLen : rightLen;
  8.     if(resbufLen < longLen) { //possible carry + string terminator
  9.         fprintf(stderr, "Not enough space for result(cur:%u)!\n", resbufLen);
  10.         return;
  11.     }
  13.     char *longAddend = isLeftLonger ? leftVal : rightVal;
  14.     char *shortAddend = isLeftLonger ? rightVal : leftVal;
  15.     unsigned int diffLen = isLeftLonger ? (leftLen-rightLen) : (rightLen-leftLen);
  16.     //a carry might be generated from adding the most significant digit
  17.     if((leftLen == rightLen) && (leftVal[0]-'0'+rightVal[0]-'0' >= 9))
  18.         resBuf += 1;
  20.     unsigned int carry = 0;
  21.     int i = longLen-1;
  22.     for(; i >= 0; i--) {
  23.         unsigned int leftAddend = longAddend[i] - '0';
  24.         unsigned int rightAddend = (i<diffLen) ? 0 : shortAddend[i-diffLen]-'0';
  25.         unsigned int digitSum = leftAddend + rightAddend + carry;
  26.         resBuf[i] = digitSum % 10 + '0';
  27.         carry = (digitSum >= 10) ? 1 : 0;
  28.     }
  29.     if(carry == 1) {
  30.         resBuf -= 1;
  31.         resBuf[0] = '1';
  32.     }
  33.     else if(leftVal[0]-'0'+rightVal[0]-'0' == 9) {
  34.         resBuf -= 1;
  35.         resBuf[0] = ' '; //fail to generate a carry
  36.     }
  37. }

注意第33~36行的处理，当最高位未按期望产生进位时，原来为0的resBuf[0]被置为空格字符，否则将无法输出运算结果。当然，也可将resBuf整体前移一个元素。

减法运算相对复杂，需要根据被减数和减数的大小调整运算顺序。若被减数小于减数("11-111"或"110-111")，则交换被减数和减数后再做正常的减法运算，并且结果需添加负号前缀。此外，还需关注借位问题。

  1. void Subtraction(char *leftVal,  char *rightVal,
  2.                  char *resBuf, unsigned int resbufLen) {
  3.     int cmpVal = strcmp(leftVal, rightVal);
  4.     if(!cmpVal) {
  5.         resBuf[0] = '0';
  6.         return;
  7.     }
  9.     unsigned int leftLen = strlen(leftVal);
  10.     unsigned int rightLen = strlen(rightVal);
  11.     unsigned char isLeftLonger = 0;
  12.     if((leftLen > rightLen) ||              //100-10
  13.        (leftLen == rightLen && cmpVal > 0)) //100-101
  14.         isLeftLonger = 1;
  15.     unsigned int longLen = isLeftLonger ? leftLen : rightLen;
  16.     if(resbufLen <= longLen) { //string terminator
  17.         fprintf(stderr, "Not enough space for result(cur:%u)!\n", resbufLen);
  18.         return;
  19.     }
  21.     char *minuend = isLeftLonger ? leftVal : rightVal;
  22.     char *subtrahend = isLeftLonger ? rightVal : leftVal;
  23.     unsigned int diffLen = isLeftLonger ? (leftLen-rightLen) : (rightLen-leftLen);
  24.     //a borrow will be generated from subtracting the most significant digit
  25.     if(!isLeftLonger) {
  26.         resBuf[0] = '-';
  27.         resBuf += 1;
  28.     }
  30.     unsigned int borrow = 0;
  31.     int i = longLen-1;
  32.     for(; i >= 0; i--)
  33.     {
  34.         unsigned int expanSubtrahend = (i<diffLen) ? '0' : subtrahend[i-diffLen];
  35.         int digitDif = minuend[i] - expanSubtrahend - borrow;
  36.         borrow = (digitDif < 0) ? 1 : 0;
  37.         resBuf[i] = digitDif + borrow*10 + '0';
  38.         //printf("[%d]Dif=%d=%c-%c-%d -> %c\n", i, digitDif, minuend[i], expanSubtrahend, borrow, resBuf[i]);
  39.     }
  41.     //strip leading '0' characters
  42.     int iSrc = 0, iDst = 0, isStripped = 0;
  43.     while(resBuf[iSrc] !='\0') {
  44.         if(isStripped) {
  45.             resBuf[iDst] = resBuf[iSrc];
  46.             iSrc++; iDst++;
  47.         }
  48.         else if(resBuf[iSrc] != '0') {
  49.             resBuf[iDst] = resBuf[iSrc];
  50.             iSrc++; iDst++;
  51.             isStripped = 1;
  52.         }
  53.         else
  54.             iSrc++;
  55.      }
  56.      resBuf[iDst] = '\0';
  57. }

对于Addition()和Subtraction()函数，设计测试用例如下：

  1. #include<assert.h>
  2. #define ASSERT_ADD(_add1, _add2, _sum) do{\
  3.     char resBuf[100] = {0}; \
  4.     Addition(_add1, _add2, resBuf, sizeof(resBuf)); \
  5.     assert(!strcmp(resBuf, _sum)); \
  6. }while(0)
  7. #define ASSERT_SUB(_minu, _subt, _dif) do{\
  8.     char resBuf[100] = {0}; \
  9.     Subtraction(_minu, _subt, resBuf, sizeof(resBuf)); \
  10.     assert(!strcmp(resBuf, _dif)); \
  11. }while(0)
  12. void VerifyOperation(void) {
  13.     ASSERT_ADD("22", "1686486458", "1686486480");
  14.     ASSERT_ADD("8888888888888", "1112", "8888888890000");
  15.     ASSERT_ADD("1234567890123", "1", "1234567890124");
  16.     ASSERT_ADD("1234567890123", "3333333333333", "4567901223456");
  17.     ASSERT_ADD("1234567890123", "9000000000000", "10234567890123");
  18.     ASSERT_ADD("1234567890123", "8867901223000", "10102469113123");
  19.     ASSERT_ADD("1234567890123", "8000000000000", " 9234567890123");
  20.     ASSERT_ADD("1377083362513770833626", "1585054852315850548524", "2962138214829621382150");
  22.     ASSERT_SUB("10012345678890", "1", "10012345678889");
  23.     ASSERT_SUB("1", "10012345678890", "-10012345678889");
  24.     ASSERT_SUB("10012345678890", "10012345678891", "-1");
  25.     ASSERT_SUB("10012345678890", "10012345686945", "-8055");
  26.     ASSERT_SUB("1000000000000", "999999999999", "1");
  27. }

考虑到语言内置的运算效率应该更高，因此在不可能产生溢出时尽量选用内置运算。CalcOperation()函数便采用这一思路：

  1. void CalcOperation(MATH_OPER *mathOper, char *resBuf, unsigned int resbufLen) {
  2.     unsigned int leftLen = strlen(mathOper->leftVal);
  3.     unsigned int rightLen = strlen(mathOper->rightVal);
  5.     switch(mathOper->operator) {
  6.         case '+':
  7.             if(leftLen <= ADD_THRES && rightLen <= ADD_THRES)
  8.                 snprintf(resBuf, resbufLen, "%d",
  9.                          atoi(mathOper->leftVal) + atoi(mathOper->rightVal));
  10.             else
  11.                 Addition(mathOper->leftVal, mathOper->rightVal, resBuf, resbufLen);
  12.             break;
  13.         case '-':
  14.             if(leftLen <= OTH_THRES && rightLen <= OTH_THRES)
  15.                 snprintf(resBuf, resbufLen, "%d",
  16.                          atoi(mathOper->leftVal) - atoi(mathOper->rightVal));
  17.             else
  18.                 Subtraction(mathOper->leftVal, mathOper->rightVal, resBuf, resbufLen);
  19.             break;
  20.         case '*':
  21.             if(leftLen <= MUL_THRES && rightLen <= MUL_THRES)
  22.                 snprintf(resBuf, resbufLen, "%d",
  23.                          atoi(mathOper->leftVal) * atoi(mathOper->rightVal));
  24.             else
  25.                 break; //Multiplication: product = multiplier * multiplicand
  26.             break;
  27.         case '/':
  28.             if(leftLen <= OTH_THRES && rightLen <= OTH_THRES)
  29.                 snprintf(resBuf, resbufLen, "%d",
  30.                          atoi(mathOper->leftVal) / atoi(mathOper->rightVal));
  31.             else
  32.                 break; //Division: quotient = dividend / divisor
  33.             break;
  34.         default:
  35.             break;
  36.     }
  38.     return;
  39. }

注意，大整数的乘法和除法运算尚未实现，因此相应代码分支直接返回。

最后，完成入口函数：

  1. int main(void) {
  2.     VerifyOperation();
  4.     char leftVal[100] = {0}, rightVal[100] = {0}, operator='+';
  5.     char resBuf[1000] = {0};
  7.     //As you see, basically any key can quit:)
  8.     printf("Enter math expression(press q to quit): ");
  9.     while(scanf(" %[0-9] %[+-*/] %[0-9]", leftVal, &operator, rightVal) == 3) {
  10.         MATH_OPER mathOper = {leftVal, rightVal, operator};
  11.         memset(resBuf, 0, sizeof(resBuf));
  12.         CalcOperation(&mathOper, resBuf, sizeof(resBuf));
  13.         printf("%s %c %s = %s\n", leftVal, operator, rightVal, resBuf);
  14.         printf("Enter math expression(press q to quit): ");
  15.     }
  16.     return 0;
  17. }

上述代码中，scanf()函数的格式化字符串风格类似正则表达式。其详细介绍参见《sscanf的字符串格式化用法》一文。

三. 效果验证

将上节代码存为BigIntOper.c文件。测试结果如下：

  1. [wangxiaoyuan_@localhost ~]$ gcc -Wall -o BigIntOper BigIntOper.c
  2. [wangxiaoyuan_@localhost ~]$ ./BigIntOper                        
  3. Enter math expression(press q to quit): 100+901
  4. 100 + 901 = 1001
  5. Enter math expression(press q to quit): 100-9
  6. 100 - 9 = 91
  7. Enter math expression(press q to quit): 1234567890123 + 8867901223000
  8. 1234567890123 + 8867901223000 = 10102469113123
  9. Enter math expression(press q to quit): 1377083362513770833626 - 1585054852315850548524
  10. 1377083362513770833626 - 1585054852315850548524 = -207971489802079714898
  11. Enter math expression(press q to quit): q
  12. [wangxiaoyuan_@localhost ~]$

通过内部测试用例和外部人工校验，可知运算结果正确无误。

添加新批注
在作者公开此批注前，只有你和作者可见。
回复批注