C語(yǔ)言實(shí)現(xiàn)大整數(shù)加減運(yùn)算詳解

更新時(shí)間：2016年08月15日 09:39:11 投稿：daisy

大數(shù)運(yùn)算，顧名思義，就是很大的數(shù)值的數(shù)進(jìn)行一系列的運(yùn)算。本文通過實(shí)例演示如何進(jìn)行C語(yǔ)言中的大整數(shù)加減運(yùn)算，有需要的可以參考借鑒。

前言

我們知道，在數(shù)學(xué)中，數(shù)值的大小是沒有上限的，但是在計(jì)算機(jī)中，由于字長(zhǎng)的限制，計(jì)算機(jī)所能表示的范圍是有限的，當(dāng)我們對(duì)比較小的數(shù)進(jìn)行運(yùn)算時(shí)，如：1234+5678，這樣的數(shù)值并沒有超出計(jì)算機(jī)的表示范圍，所以可以運(yùn)算。但是當(dāng)我們?cè)趯?shí)際的應(yīng)用中進(jìn)行大量的數(shù)據(jù)處理時(shí)，會(huì)發(fā)現(xiàn)參與運(yùn)算的數(shù)往往超過計(jì)算機(jī)的基本數(shù)據(jù)類型的表示范圍，比如說，在天文學(xué)上，如果一個(gè)星球距離我們?yōu)?00萬(wàn)光年，那么我們將其化簡(jiǎn)為公里，或者是米的時(shí)候，我們會(huì)發(fā)現(xiàn)這是一個(gè)很大的數(shù)。這樣計(jì)算機(jī)將無(wú)法對(duì)其進(jìn)行直接計(jì)算。

可能我們認(rèn)為實(shí)際應(yīng)用中的大數(shù)也不過就是幾百位而已，實(shí)際上，在某些領(lǐng)域里，甚至可能出現(xiàn)幾百萬(wàn)位的數(shù)據(jù)進(jìn)行運(yùn)算，這是我們很難想象的。如果沒有計(jì)算機(jī)，那么計(jì)算效率可想而知。

由于編程語(yǔ)言提供的基本數(shù)值數(shù)據(jù)類型表示的數(shù)值范圍有限，不能滿足較大規(guī)模的高精度數(shù)值計(jì)算，因此需要利用其他方法實(shí)現(xiàn)高精度數(shù)值的計(jì)算，于是產(chǎn)生了大數(shù)運(yùn)算。本項(xiàng)目實(shí)現(xiàn)了大數(shù)運(yùn)算的加、減運(yùn)算。

一. 問題提出

用C語(yǔ)言實(shí)現(xiàn)一個(gè)大整數(shù)計(jì)算器。初步要求支持大整數(shù)的加、減運(yùn)算，例如8888888888888+1112=8888888890000或1000000000000-999999999999=1。

C語(yǔ)言中，整型變量所能存儲(chǔ)的最寬數(shù)據(jù)為0xFFFF FFFF，對(duì)應(yīng)的無(wú)符號(hào)數(shù)為4294967295，即無(wú)法保存超過10位的整數(shù)。注意，此處"10位"指數(shù)學(xué)中的10個(gè)數(shù)字，并非計(jì)算機(jī)科學(xué)中的10比特。浮點(diǎn)類型double雖然可以存儲(chǔ)更多位數(shù)的整數(shù)，但一方面常數(shù)字面量寬度受編譯器限制，另一方面通過浮點(diǎn)方式處理整數(shù)精度較低。例如：

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

輸出為res = 2962138214829621510144，而正確值應(yīng)為2962138214829621382150。

既然基本數(shù)據(jù)類型無(wú)法表示大整數(shù)，那么只能自己設(shè)計(jì)存儲(chǔ)方式來實(shí)現(xiàn)大整數(shù)的表示和運(yùn)算。通常，輸入的大整數(shù)為字符串形式。因此，常見的思路是將大整數(shù)字符串轉(zhuǎn)化為數(shù)組，再用數(shù)組模擬大整數(shù)的運(yùn)算。具體而言，先將字符串中的數(shù)字字符順序存入一個(gè)較大的整型數(shù)組，其元素代表整數(shù)的某一位或某幾位(如萬(wàn)進(jìn)制)；然后根據(jù)運(yùn)算規(guī)則操作數(shù)組元素，以模擬整數(shù)運(yùn)算；最后，將數(shù)組元素順序輸出。

數(shù)組方式操作方便，實(shí)現(xiàn)簡(jiǎn)單，缺點(diǎn)是空間利用率和執(zhí)行效率不高。也可直接操作大整數(shù)字符串，從字符串末尾逆向計(jì)算。本文實(shí)現(xiàn)就采用這種方式。

二. 代碼實(shí)現(xiàn)

首先，給出幾個(gè)宏定義和運(yùn)算結(jié)構(gòu)：

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

#define ADD_THRES   (sizeof("4294967295")-2) //兩個(gè)9位整數(shù)相加不會(huì)溢出
#define MUL_THRES   (sizeof("65535")-2)    //兩個(gè)4位整數(shù)相乘不會(huì)溢出
#define OTH_THRES   (sizeof("4294967295")-1) //兩個(gè)10位整數(shù)相減或相除不會(huì)溢出

typedef struct{
  char *leftVal;
  char *rightVal;
  char operator;
}MATH_OPER;

基于上述定義，以下將依次給出運(yùn)算代碼的實(shí)現(xiàn)。

加法運(yùn)算主要關(guān)注相加過程中的進(jìn)位問題：

void Addition(char *leftVal, char *rightVal,
       char *resBuf, unsigned int resbufLen) {
  unsigned int leftLen = strlen(leftVal);
  unsigned int rightLen = strlen(rightVal);

  unsigned char isLeftLonger = (leftLen>=rightLen) ? 1 : 0;
  unsigned int longLen = isLeftLonger ? leftLen : rightLen;
  if(resbufLen < longLen) { //possible carry + string terminator
    fprintf(stderr, "Not enough space for result(cur:%u)!\n", resbufLen);
    return;
  }

  char *longAddend = isLeftLonger ? leftVal : 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) && (leftVal[0]-'0'+rightVal[0]-'0' >= 9))
    resBuf += 1;

  unsigned int carry = 0;
  int i = longLen-1;
  for(; i >= 0; i--) {
    unsigned int leftAddend = longAddend[i] - '0';
    unsigned int rightAddend = (i<diffLen) ? 0 : shortAddend[i-diffLen]-'0';
    unsigned int digitSum = leftAddend + rightAddend + carry;
    resBuf[i] = digitSum % 10 + '0';
    carry = (digitSum >= 10) ? 1 : 0;
  }
  if(carry == 1) {
    resBuf -= 1;
    resBuf[0] = '1';
  }
  else if(leftVal[0]-'0'+rightVal[0]-'0' == 9) {
    resBuf -= 1;
    resBuf[0] = ' '; //fail to generate a carry
  }
}

注意第33~36行的處理，當(dāng)最高位未按期望產(chǎn)生進(jìn)位時(shí)，原來為0的resBuf[0]被置為空格字符，否則將無(wú)法輸出運(yùn)算結(jié)果。當(dāng)然，也可將resBuf整體前移一個(gè)元素。

減法運(yùn)算相對(duì)復(fù)雜，需要根據(jù)被減數(shù)和減數(shù)的大小調(diào)整運(yùn)算順序。若被減數(shù)小于減數(shù)("11-111"或"110-111")，則交換被減數(shù)和減數(shù)后再做正常的減法運(yùn)算，并且結(jié)果需添加負(fù)號(hào)前綴。此外，還需關(guān)注借位問題。

void Subtraction(char *leftVal, char *rightVal,
         char *resBuf, unsigned int resbufLen) {
  int cmpVal = strcmp(leftVal, rightVal);
  if(!cmpVal) {
    resBuf[0] = '0';
    return;
  }

  unsigned int leftLen = strlen(leftVal);
  unsigned int rightLen = strlen(rightVal);
  unsigned char isLeftLonger = 0;
  if((leftLen > rightLen) ||       //100-10
    (leftLen == rightLen && cmpVal > 0)) //100-101
    isLeftLonger = 1;
  unsigned int longLen = isLeftLonger ? leftLen : rightLen;
  if(resbufLen <= longLen) { //string terminator
    fprintf(stderr, "Not enough space for result(cur:%u)!\n", resbufLen);
    return;
  }

  char *minuend = isLeftLonger ? leftVal : rightVal;
  char *subtrahend = isLeftLonger ? rightVal : leftVal;
  unsigned int diffLen = isLeftLonger ? (leftLen-rightLen) : (rightLen-leftLen);
  //a borrow will be generated from subtracting the most significant digit
  if(!isLeftLonger) {
    resBuf[0] = '-';
    resBuf += 1;
  }

  unsigned int borrow = 0;
  int i = longLen-1;
  for(; i >= 0; i--)
  {
    unsigned int expanSubtrahend = (i<diffLen) ? '0' : subtrahend[i-diffLen];
    int digitDif = 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]);
  }

  //strip leading '0' characters
  int iSrc = 0, iDst = 0, isStripped = 0;
  while(resBuf[iSrc] !='\0') {
    if(isStripped) {
      resBuf[iDst] = resBuf[iSrc];
      iSrc++; iDst++;
    }
    else if(resBuf[iSrc] != '0') {
      resBuf[iDst] = resBuf[iSrc];
      iSrc++; iDst++;
      isStripped = 1;
    }
    else
      iSrc++;
   }
   resBuf[iDst] = '\0';
}

對(duì)于Addition()和Subtraction()函數(shù)，設(shè)計(jì)測(cè)試用例如下：

#include<assert.h>
#define ASSERT_ADD(_add1, _add2, _sum) do{\
  char resBuf[100] = {0}; \
  Addition(_add1, _add2, resBuf, sizeof(resBuf)); \
  assert(!strcmp(resBuf, _sum)); \
}while(0)
#define ASSERT_SUB(_minu, _subt, _dif) do{\
  char resBuf[100] = {0}; \
  Subtraction(_minu, _subt, resBuf, sizeof(resBuf)); \
  assert(!strcmp(resBuf, _dif)); \
}while(0)
void VerifyOperation(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");
}

考慮到語(yǔ)言內(nèi)置的運(yùn)算效率應(yīng)該更高，因此在不可能產(chǎn)生溢出時(shí)盡量選用內(nèi)置運(yùn)算。CalcOperation()函數(shù)便采用這一思路：

void CalcOperation(MATH_OPER *mathOper, char *resBuf, unsigned int resbufLen) {
  unsigned int leftLen = strlen(mathOper->leftVal);
  unsigned int rightLen = 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;
}

注意，大整數(shù)的乘法和除法運(yùn)算尚未實(shí)現(xiàn)，因此相應(yīng)代碼分支直接返回。

最后，完成入口函數(shù)：

int main(void) {
  VerifyOperation();

  char leftVal[100] = {0}, rightVal[100] = {0}, operator='+';
  char resBuf[1000] = {0};
  
  //As you see, 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 = %s\n", leftVal, operator, rightVal, resBuf);
    printf("Enter math expression(press q to quit): ");
  }
  return 0;
}

上述代碼中，scanf()函數(shù)的格式化字符串風(fēng)格類似正則表達(dá)式。其詳細(xì)介紹參見《sscanf的字符串格式化用法》一文。

三. 效果驗(yàn)證

將上節(jié)代碼存為BigIntOper.c文件。測(cè)試結(jié)果如下：

[wangxiaoyuan_@localhost ~]$ gcc -Wall -o BigIntOper BigIntOper.c
[wangxiaoyuan_@localhost ~]$ ./BigIntOper            
Enter math expression(press q to quit): 100+901
100 + 901 = 1001
Enter math expression(press q to quit): 100-9
100 - 9 = 91
Enter math expression(press q to quit): 1234567890123 + 8867901223000
1234567890123 + 8867901223000 = 10102469113123
Enter math expression(press q to quit): 1377083362513770833626 - 1585054852315850548524
1377083362513770833626 - 1585054852315850548524 = -207971489802079714898
Enter math expression(press q to quit): q
[wangxiaoyuan_@localhost ~]$

通過內(nèi)部測(cè)試用例和外部人工校驗(yàn)，可知運(yùn)算結(jié)果正確無(wú)誤。

總結(jié)

以上就是C語(yǔ)言實(shí)現(xiàn)大整數(shù)加減運(yùn)算的全部?jī)?nèi)容，大家都學(xué)會(huì)了嗎？希望本文的內(nèi)容對(duì)大家學(xué)習(xí)C語(yǔ)言能有所幫助。

您可能感興趣的文章: