C說話完成年夜整數加減運算詳解

C說話完成年夜整數加減運算詳解。本站提示廣大學習愛好者：（C說話完成年夜整數加減運算詳解）文章只能為提供參考，不一定能成為您想要的結果。以下是C說話完成年夜整數加減運算詳解正文

媒介

    我們曉得，在數學中，數值的年夜小是沒有下限的，然則在盤算機中，因為字長的限制，盤算機所能表現的規模是無限的，當我們比較較小的數停止運算時，如：1234+5678，如許的數值並沒有超越盤算機的表現規模，所以可以運算。然則當我們在現實的運用中停止年夜量的數據處置時，會發明介入運算的數常常跨越盤算機的根本數據類型的表現規模，好比說，在地理學上，假如一個星球間隔我們為100萬光年，那末我們將其化簡為千米，或許是米的時刻，我們會發明這是一個很年夜的數。如許盤算機將沒法對其停止直接盤算。

    能夠我們以為現實運用中的年夜數也不外就是幾百位罷了，現實上，在某些范疇裡，乃至能夠湧現幾百萬位的數據停止運算，這是我們很難想象的。假如沒有盤算機，那末盤算效力可想而知。

    因為編程說話供給的根本數值數據類型表現的數值規模無限，不克不及知足較年夜范圍的高精度數值盤算，是以須要應用其他辦法完成高精度數值的盤算，因而發生了年夜數運算。本項目完成了年夜數運算的加、減運算。

一. 成績提出

用C說話完成一個年夜整數盤算器。初步請求支撐年夜整數的加、減運算，例如8888888888888+1112=8888888890000或1000000000000-999999999999=1。

C說話中，整型變量所能存儲的最寬數據為0xFFFF FFFF，對應的無符號數為4294967295，即沒法保留跨越10位的整數。留意，此處"10位"指數學中的10個數字，並不是盤算機迷信中的10比特。浮點類型double固然可以存儲更多位數的整數，但一方面常數字面量寬度受編譯器限制，另外一方面經由過程浮點方法處置整數精度較低。例如：

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

輸入為res = 2962138214829621510144，而准確值應為2962138214829621382150。

既然根本數據類型沒法表現年夜整數，那末只能本身設計存儲方法來完成年夜整數的表現和運算。平日，輸出的年夜整數為字符串情勢。是以，罕見的思緒是將年夜整數字符串轉化為數組，再用數組模仿年夜整數的運算。詳細而言，先將字符串中的數字字符次序存入一個較年夜的整型數組，其元素代表整數的某一名或某幾位(如萬進制)；然後依據運算規矩操作數組元素，以模仿整數運算；最初，將數組元素次序輸入。

數組方法操作便利，完成簡略，缺陷是空間應用率和履行效力不高。也可直接操作年夜整數字符串，從字符串末尾逆向盤算。本文完成就采取這類方法。

二. 代碼完成

起首，給出幾個宏界說和運算構造：

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

#define ADD_THRES   (sizeof("4294967295")-2) //兩個9位整數相加不會溢出
#define MUL_THRES   (sizeof("65535")-2)    //兩個4位整數相乘不會溢出
#define OTH_THRES   (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 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行的處置，當最高位未定期望發生進位時，本來為0的resBuf[0]被置為空格字符，不然將沒法輸入運算成果。固然，也可將resBuf全體前移一個元素。

減法運算絕對龐雜，須要依據被減數和減數的年夜小調劑運算次序。若被減數小於減數("11-111"或"110-111")，則交流被減數和減數後再做正常的減法運算，而且成果需添加負號前綴。另外，還需存眷借位成績。

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';
}

關於Addition()和Subtraction()函數，設計測試用例以下：

#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");
}

斟酌到說話內置的運算效力應當更高，是以在弗成能發生溢出時盡可能選用內置運算。CalcOperation()函數便采取這一思緒：

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;
}

留意，年夜整數的乘法和除法運算還沒有完成，是以響應代碼分支直接前往。

最初，完成進口函數：

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()函數的格局化字符串作風相似正則表達式。其具體引見拜見《sscanf的字符串格局化用法》一文。

三. 後果驗證

將上節代碼存為BigIntOper.c文件。測試成果以下：

[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 ~]$ 

經由過程外部測試用例和內部人工校驗，可知運算成果准確無誤。

總結

以上就是C說話完成年夜整數加減運算的全體內容，年夜家都學會了嗎？願望本文的內容對年夜家進修C說話能有所贊助。