前言
我們知道，在數學中，數值的大小是沒有上限的，但是在計算機中，由于字長的限制，計算機所能表示的范圍是有限的，當我們對比較小的數進行運算時，如：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+901100 + 901 = 1001Enter math expression(press q to quit): 100-9100 - 9 = 91Enter math expression(press q to quit): 1234567890123 + 88679012230001234567890123 + 8867901223000 = 10102469113123Enter math expression(press q to quit): 1377083362513770833626 - 15850548523158505485241377083362513770833626 - 1585054852315850548524 = -207971489802079714898Enter math expression(press q to quit): q[wangxiaoyuan_@localhost ~]$
通過內部測試用例和外部人工校驗，可知運算結果正確無誤。
總結
以上就是C語言實現大整數加減運算的全部內容，大家都學會了嗎？希望本文的內容對大家學習C語言能有所幫助。
新聞熱點
疑難解答
圖片精選
