C語言實(shí)現(xiàn)大整數(shù)加減運(yùn)算詳解
前言
我們知道,在數(shù)學(xué)中,數(shù)值的大小是沒有上限的,但是在計(jì)算機(jī)中,由于字長的限制,計(jì)算機(jī)所能表示的范圍是有限的,當(dāng)我們對比較小的數(shù)進(jìn)行運(yùn)算時(shí),如:1234+5678,這樣的數(shù)值并沒有超出計(jì)算機(jī)的表示范圍,所以可以運(yùn)算。但是當(dāng)我們在實(shí)際的應(yīng)用中進(jìn)行大量的數(shù)據(jù)處理時(shí),會(huì)發(fā)現(xiàn)參與運(yùn)算的數(shù)往往超過計(jì)算機(jī)的基本數(shù)據(jù)類型的表示范圍,比如說,在天文學(xué)上,如果一個(gè)星球距離我們?yōu)?00萬光年,那么我們將其化簡為公里,或者是米的時(shí)候,我們會(huì)發(fā)現(xiàn)這是一個(gè)很大的數(shù)。這樣計(jì)算機(jī)將無法對其進(jìn)行直接計(jì)算。
可能我們認(rèn)為實(shí)際應(yīng)用中的大數(shù)也不過就是幾百位而已,實(shí)際上,在某些領(lǐng)域里,甚至可能出現(xiàn)幾百萬位的數(shù)據(jù)進(jìn)行運(yùn)算,這是我們很難想象的。如果沒有計(jì)算機(jī),那么計(jì)算效率可想而知。
由于編程語言提供的基本數(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語言實(shí)現(xiàn)一個(gè)大整數(shù)計(jì)算器。初步要求支持大整數(shù)的加、減運(yùn)算,例如8888888888888+1112=8888888890000或1000000000000-999999999999=1。
C語言中,整型變量所能存儲(chǔ)的最寬數(shù)據(jù)為0xFFFF FFFF,對應(yīng)的無符號(hào)數(shù)為4294967295,即無法保存超過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ù)類型無法表示大整數(shù),那么只能自己設(shè)計(jì)存儲(chǔ)方式來實(shí)現(xiàn)大整數(shù)的表示和運(yùn)算。通常,輸入的大整數(shù)為字符串形式。因此,常見的思路是將大整數(shù)字符串轉(zhuǎn)化為數(shù)組,再用數(shù)組模擬大整數(shù)的運(yùn)算。具體而言,先將字符串中的數(shù)字字符順序存入一個(gè)較大的整型數(shù)組,其元素代表整數(shù)的某一位或某幾位(如萬進(jìn)制);然后根據(jù)運(yùn)算規(guī)則操作數(shù)組元素,以模擬整數(shù)運(yùn)算;最后,將數(shù)組元素順序輸出。
數(shù)組方式操作方便,實(shí)現(xià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]被置為空格字符,否則將無法輸出運(yùn)算結(jié)果。當(dāng)然,也可將resBuf整體前移一個(gè)元素。
減法運(yùn)算相對復(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'; }
對于Addition()
和Subtraction()
函數(shù),設(shè)計(jì)測試用例如下:
#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"); }
考慮到語言內(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
文件。測試結(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)部測試用例和外部人工校驗(yàn),可知運(yùn)算結(jié)果正確無誤。
總結(jié)
以上就是C語言實(shí)現(xiàn)大整數(shù)加減運(yùn)算的全部內(nèi)容,大家都學(xué)會(huì)了嗎?希望本文的內(nèi)容對大家學(xué)習(xí)C語言能有所幫助。
相關(guān)文章
Unix下C程序內(nèi)存泄漏檢測工具Valgrind的安裝與使用詳解
以下是對Unix下C程序內(nèi)存泄漏檢測工具Valgrind的安裝與使用進(jìn)行了詳細(xì)的分析介紹,需要的朋友可以過來參考下2013-08-08C實(shí)現(xiàn)與 uint64_t 相同功能的類
本文給大家分享的是筆者實(shí)現(xiàn)的仿uint64_t的類,可以用在不支持uint64_t的平臺(tái)上,雖然現(xiàn)在功能還不完善,但是還是分享給大家,也算是給大家一個(gè)思路吧。2015-12-12VSCode搭建STM32開發(fā)環(huán)境的方法步驟
當(dāng)我們的工程文件比較大的時(shí)候,編譯一次代碼需要很久可能會(huì)花費(fèi)到四五分鐘,但是我們用vscode編寫和編譯的話時(shí)間就會(huì)大大縮減,本文就介紹一下VSCode搭建STM32開發(fā)環(huán)境,感興趣的可以了解一下2021-07-07STL priority_queue(優(yōu)先隊(duì)列)詳解
這篇文章主要介紹了 STL priority_queue(優(yōu)先隊(duì)列)詳解的相關(guān)資料,需要的朋友可以參考下2016-10-10