C語言實現大數計算器

一、實驗介紹

1.1 實驗內容

本實驗通過使用C語言實現一個簡易計算器，該計算器能夠進行任意長度的有符號整數的加、減、乘、除運算。

1.2 實驗知識點

• c語言大數加法實現
• c語言大數減法實現
• c語言大數乘法實現
• c語言大數除法實現

1.3 實驗環境

• vim
• gcc 編譯器
• Xfce終端

1.4 適合人群

本課程適合已了解C語言基礎語法規則，并期望通過實際編程項目進行演練，以提高C語言編程技巧的用戶進行學習。

1.5 代碼獲取

你可以通過下面命令將代碼下載到實驗樓環境中，作為參照對比進行學習。

$ wget http://labfile.oss.aliyuncs.com/courses/750/calculator_sample.tar.gz $ tar xvf calculator_sample.tar.gz

二、實驗步驟

2.1 如何表示大數

由于C語言的基本數據類型在表示數字大小時都有一定的限制，所以要在C語言中表示一個大數，有兩種方式：字符串和自行構造數據結構。

字符串表示，適合人解讀，但不適用于機器運算

數據結構表示，適用于機器運算，但人對其進行解讀比較困難

我們的設計，綜合考慮上述兩種方式的優缺點，我們自行構造數據用于表示大數以提供給機器進行運算，同時提供字符串與我們構造的數據結構進行互轉的輔助性函數:

// 大數數據結構 typedef struct bignumber_s{char sign; // 代表大數的符號，1為負數，0為正數int len; // 代表大數的位數char data[]; // 大數的數據內容，data[0]代表個位，data[1]代表十位，data[2]代表百位.... } bignumber_s;// 構造大數模板，len指向大數的數據位數，sign表示該大數的符號 bignumber_s *make_bignumber_temp(int len, int sign); // 從字符串構造一個大數 bignumber_s *make_bignumber_fromstr(const char *str); // 以字符串的形式打印輸出一個大數 void print_bignumber(bignumber_s* b);

在bignumber_s數據結構的定義中，我們使用了C語言里一種稱為柔性數組的技巧，感興趣的同學可以自行研究。

下圖演示了我們的bignumber_s如何表示"-123"這個數：

實現make_bignumber_temp函數：

// 構造大數模板，len指向大數的數據位數，sign表示該大數的符號 bignumber_s *make_bignumber_temp(int len, int sign) {// 分配bignumber_s及其所代表數據 所需的內存bignumber_s *temp = malloc(sizeof(bignumber_s)+len);if (NULL == temp) {perror("Malloc");exit(-1);}temp->sign = sign;temp->len = len;memset(temp->data, 0, len);return temp; }

實現make_bignumber_fromstr函數：

// 從字符串構造一個大數 bignumber_s *make_bignumber_fromstr(const char *str) {// 處理負數字符串，即"-123"int sign = 0;if (str[0]=='-') {sign = 1;str++;}// 處理數字字符串冗余的0，即"00123" -> "123"const char * striped_str = strip_str(str);int len = strlen(striped_str);// 指定數據位長度即符號，創建一個大數模板bignumber_s *temp = make_bignumber_temp(len ,sign);// 將字符串數據填充進模板中，完成大數創建fill_data_fromstr(temp, striped_str);return temp; } // 處理數字字符串冗余的0，即"00123" -> "123" const char *strip_str(const char *str) {int i = 0;int len = strlen(str);for (i=0; i<len-1&&str[i]=='0'; i++) ;return str+i; } // 將字符串數據填充進模板中 void fill_data_fromstr(bignumber_s *n, const char *str) {int i = 0;int len = n->len;for (i=0; i<len; i++) {int d = str[len-1-i]-'0';if (d>=0 && d<=9) n->data[i] = d;else {fprintf(stderr, "Invalid Number:%s\n", str);exit(-1);}} }

實現print_bignumber函數：

// 以字符串的形式打印輸出一個大數 void print_bignumber(bignumber_s* b) {int len = b->len;char *str = malloc(len+1);int i = 0;for (i=0; i<len; i++) {str[i] = b->data[len-i-1]+'0';}str[len] = '\0';fprintf(stdout,"%s%s\n", b->sign==1?"-":"", strip_str(str));free(str); }

2.2 實現計算器的殼

我們的計算器最終編譯生成為一個名為calculator的可執行程序，使用計算器的方法如下：

$ ./calculator 123 + 123 # 執行加法運算 $ ./calculator 123 - 123 # 執行減法運算 $ ./calculator 123 x 123 # 執行乘法運算 $ ./calculator 123 / 123 # 執行除法運算

實現我們的main函數：

void usage(const char *s) {fprintf(stderr, "Usage:%s number1 op(+-x/) number2.\n",s);exit(-1); }bignumber_s *calc_add(bignumber_s *a, bignumber_s *b) {// 實現加法 } bignumber_s *calc_sub(bignumber_s *a, bignumber_s *b) {// 實現減法 } bignumber_s *calc_mul(bignumber_s *a, bignumber_s *b) {// 實現乘法 } bignumber_s *calc_div(bignumber_s *a, bignumber_s *b) {// 實現除法 } int main(int argc, char *argv[]) {bignumber_s *a = make_bignumber_fromstr(argv[1]);bignumber_s *b = make_bignumber_fromstr(argv[3]);if (argc!=4) usage(argv[0]);if (0 == strcmp(argv[2],"+"))print_bignumber(calc_add(a,b));else if (0 == strcmp(argv[2],"-"))print_bignumber(calc_sub(a,b));else if (0 == strcmp(argv[2],"x"))print_bignumber(calc_mul(a,b));else if (0 == strcmp(argv[2],"/"))print_bignumber(calc_div(a,b));else usage(argv[0]);return 0; }

2.3 實現無符號加減法

2.3.1 實現無符號加法

加法的實現比較簡單，我們借鑒小學時學過的豎式計算過程的思路：

思路大致是：

從最低位開始，對應位置相加，和大于10的向高位進位，取個位數為該位置相加的和

對應位置相加時，要加上來自低位的進位值

n位數+m位數，其和最大為max(n,m)+1位數

實現無符號加法：

#define BASE (10) #define MAX(x,y) ((x)>(y)?(x):(y)) // 實現無符號加法，a和b為加數，r為和 void add_impl(bignumber_s *a, bignumber_s *b, bignumber_s *r) {int i = 0;char carry = 0;int len = r->len;for (i=0; i<len; i++) {if (i<a->len)carry += a->data[i];if (i<b->len)carry += b->data[i];r->data[i] = carry%BASE;carry /= BASE;} }bignumber_s *add(bignumber_s *a, bignumber_s *b) {// n位數+m位數，其和最大為max(n,m)+1位數int len = MAX(a->len, b->len) + 1;bignumber_s *result = make_bignumber_temp(len,a->sign);// add_impl(a,b,result);return result; }

2.3.2 實現無符號減法

減法的實現與加法的實現思路相似，依舊請出的我們豎式計數法：

思路大致是：

從最低位開始，對應位置相減，不夠減的向高位借位，得到的差作為該位置的差

對應位置相減時，要減去來自低位的借位值

n位數-m位數，其和最大為n位數

實現無符號減法：

// 實現無符號減法，a-b , r為差 void sub_impl(bignumber_s *a, bignumber_s *b, bignumber_s *r) {int i=0;int borrow = 0;int len = r->len;int temp = 0;for (i=0; i<len; i++) {temp = a->data[i]+BASE-borrow-((i<b->len)?b->data[i]:0);r->data[i] = temp%BASE;borrow = 1-temp/BASE;} }bignumber_s *sub(bignumber_s *a, bignumber_s *b) {int len = a->len;bignumber_s *result = make_bignumber_temp(len,0);sub_impl(a,b,result);return result; }

2.3.3 大數計算器v1版本

大數計算器v1版本:

/* * file name : calculatorv1.c * desp : calculator version 1 */ #include <stdio.h> #include <stdlib.h> #include <string.h>#define BASE (10) #define MAX(x,y) ((x)>(y)?(x):(y))// 大數數據結構 typedef struct bignumber_s{char sign; // 代表大數的符號，1為負數，0為正數int len; // 代表大數的位數char data[]; // 大數的數據內容，data[0]代表個位，data[1]代表十位，data[2]代表百位.... } bignumber_s;// 構造大數模板，len指向大數的數據位數，sign表示該大數的符號 bignumber_s *make_bignumber_temp(int len, int sign) {// 分配bignumber_s及其所代表數據 所需的內存bignumber_s *temp = malloc(sizeof(bignumber_s)+len);if (NULL == temp) {perror("Malloc");exit(-1);}temp->sign = sign;temp->len = len;memset(temp->data, 0, len);return temp; }// 處理數字字符串冗余的0，即"00123" -> "123" const char *strip_str(const char *str) {int i = 0;int len = strlen(str);for (i=0; i<len-1&&str[i]=='0'; i++) ;return str+i; } // 將字符串數據填充進模板中 void fill_data_fromstr(bignumber_s *n, const char *str) {int i = 0;int len = n->len;for (i=0; i<len; i++) {int d = str[len-1-i]-'0';if (d>=0 && d<=9) n->data[i] = d;else {fprintf(stderr, "Invalid Number:%s\n", str);exit(-1);}} } // 從字符串構造一個大數 bignumber_s *make_bignumber_fromstr(const char *str) {// 處理負數字符串，即"-123"int sign = 0;if (str[0]=='-') {sign = 1;str++;}// 處理數字字符串冗余的0，即"00123" -> "123"const char * striped_str = strip_str(str);int len = strlen(striped_str);// 指定數據位長度即符號，創建一個大數模板bignumber_s *temp = make_bignumber_temp(len ,sign);// 將字符串數據填充進模板中，完成大數創建fill_data_fromstr(temp, striped_str);return temp; }// 以字符串的形式打印輸出一個大數 void print_bignumber(bignumber_s* b) {int len = b->len;char *str = malloc(len+1);int i = 0;for (i=0; i<len; i++) {str[i] = b->data[len-i-1]+'0';}str[len] = '\0';fprintf(stdout,"%s%s\n", b->sign==1?"-":"", strip_str(str));free(str); }void usage(const char *s) {fprintf(stderr, "Usage:%s number1 +-x/ number2.\n",s);exit(-1); }// 實現無符號加法，a和b為加數，r為和 void add_impl(bignumber_s *a, bignumber_s *b, bignumber_s *r) {int i = 0;char carry = 0;int len = r->len;for (i=0; i<len; i++) {if (i<a->len)carry += a->data[i];if (i<b->len)carry += b->data[i];r->data[i] = carry%BASE;carry /= BASE;} }bignumber_s *calc_add(bignumber_s *a, bignumber_s *b) {// n位數+m位數，其和最大為max(n,m)+1位數int len = MAX(a->len, b->len) + 1;bignumber_s *result = make_bignumber_temp(len, 0);// add_impl(a,b,result);return result; }// 實現無符號減法，a-b , r為差 void sub_impl(bignumber_s *a, bignumber_s *b, bignumber_s *r) {int i=0;int borrow = 0;int len = r->len;int temp = 0;for (i=0; i<len; i++) {temp = a->data[i]+BASE-borrow-((i<b->len)?b->data[i]:0);r->data[i] = temp%BASE;borrow = temp/BASE?0:1;} }bignumber_s *calc_sub(bignumber_s *a, bignumber_s *b) {int len = a->len;bignumber_s *result = make_bignumber_temp(len,0);sub_impl(a,b,result);return result; }bignumber_s *calc_mul(bignumber_s *a, bignumber_s *b) {// 實現乘法return NULL; } bignumber_s *calc_div(bignumber_s *a, bignumber_s *b) {// 實現除法return NULL; } int main(int argc, char *argv[]) {bignumber_s *a = make_bignumber_fromstr(argv[1]);bignumber_s *b = make_bignumber_fromstr(argv[3]);if (argc!=4) usage(argv[0]);if (0 == strcmp(argv[2],"+"))print_bignumber(calc_add(a,b));else if (0 == strcmp(argv[2],"-"))print_bignumber(calc_sub(a,b));else if (0 == strcmp(argv[2],"x"))print_bignumber(calc_mul(a,b));else if (0 == strcmp(argv[2],"/"))print_bignumber(calc_div(a,b));else usage(argv[0]);return 0; }

2.3.4 演示

編譯命令：

$ gcc -o calculatorv1 calculatorv1.c

結果演示：?

可以使用python交互界面驗證我們的計算結果：

2.4 實現有符號加減法

2.4.1 有符號加法

先來看有符號的加法，假設有兩個數A和B，有符號加法分以下幾種情況：

// 情況一：A > 0 并且 B > 0 A + B --> |A| + |B| (|A|表示求A的絕對值，下同) // 情況二：A > 0 并且 B < 0 A + B --> |A| - |B| // 情況三：A < 0 并且 B > 0 A + B --> |B| - |A| // 情況四：A < 0 并且 B < 0 A + B --> -(|B| + |A|) (此處-表示取負值)

情況一和情況四可以用第2節的無符號加法求解，情況四在用加法求值后再取負值；情況二和情況三轉化為有符號減法操作。

因此我們的加法函數可以這么實現：

bignumber_s *calc_add(bignumber_s *a, bignumber_s *b) {// 情況一和情況四if (a->sign==b->sign) {// n位數+m位數，其和最大為max(n,m)+1位數int len = MAX(a->len, b->len) + 1;bignumber_s *result = make_bignumber_temp(len,a->sign);add_impl(a,b,result);return result;} else if (a->sign == 0 && b->sign == 1) {//情況二b->sign = 0; //b數去絕對值return calc_sub(a,b);} else if (a->sign == 1 && b->sign == 0) {//情況三a->sign = 0; //a數去絕對值return calc_sub(b,a);} }

2.4.2 有符號減法

接下來看有符號的減法，假設有兩個數A和B，有符號減法分以下幾種情況：

// 情況一：A > 0 并且 B > 0 A - B --> |A| - |B| (|A|表示求A的絕對值，下同) // 情況二：A > 0 并且 B < 0 A - B --> |A| + |B| // 情況三：A < 0 并且 B > 0 A - B --> -(|A| + |B|) (此處-表示取負值) // 情況四：A < 0 并且 B < 0 A - B --> |B| - |A|

情況二和情況三可以轉化為第2節的無符號加法求解，情況三在用加法求值后再取負值；

情況一，當被減數大于減數時，結果為正數，可以直接用第2節的減法實現求解；

當被減數小于減數時，結果為負數，即:

// A < B， A>=0 且B>=0 時 A - B ---> -(B-A)

情況四，將減數和被減數調換就成了情況一了。

我們需要先實現一個用以判斷兩個大數大小的輔助函數，用以判斷被減數和減數的大小：

int valid_len(bignumber_s *a) {int len = a->len;int i = len-1;for (i=len-1; i>=0; i--) {if (a->data[i]==0) len--;else break;}return len; } // 判斷兩個大數的大小 // a > b 返回1 ，a<b 返回 -1 , a==b 返回0 int cmp(bignumber_s *a, bignumber_s *b) {if (a->sign==0&&b->sign==1) return 1;if (a->sign==1&&b->sign==0) return -1;int sign = a->sign;int alen = valid_len(a);int blen = valid_len(b);if (alen>blen) return (sign==1?-1:1);else if (alen<blen) return (sign==1?1:-1);else {int i = 0;int len = alen;for (i=len-1; i>=0; i--) {if (a->data[i]>b->data[i])return (sign==1?-1:1);else if (a->data[i]<b->data[i]) return (sign==1?1:-1);}return 0;} }

有符號的減法實現如下：

bignumber_s *sub(bignumber_s *a, bignumber_s *b) {// 情況一if(a->sign==0 && b->sign==0) {if (cmp(a,b)>=0) { // 被減數大于等于減數，即差大于等于0時int len = a->len;bignumber_s *result = make_bignumber_temp(len,0);sub_impl(a,b,result);return result;} else { // 被減數小于減數，即差小于0時int len = b->len;bignumber_s *result = make_bignumber_temp(len,1);sub_impl(b,a,result);return result;}} else if (a->sign==1 && b->sign==1) { //情況四b->sign=0; a->sign=0;return sub(b,a); //調換減數和被減數，變成情況一}else if (a->sign==0 && b->sign==1) { // 情況二b->sign=0;bignumber_s *result = add(a,b);result->sign = 0;return result; } else if (a->sign==1 && b->sign==0) { // 情況三a->sign=0;bignumber_s *result = add(a,b);result->sign = 1;return result; } }

2.4.3 大數計算器v2版本

完整代碼如下(calculatorv2.c):

/* * file name : calculatorv2.c * desp : calculator version 2 */ #include <stdio.h> #include <stdlib.h> #include <string.h>#define BASE (10) #define MAX(x,y) ((x)>(y)?(x):(y))// 大數數據結構 typedef struct bignumber_s{char sign; // 代表大數的符號，1為負數，0為正數int len; // 代表大數的位數char data[]; // 大數的數據內容，data[0]代表個位，data[1]代表十位，data[2]代表百位.... } bignumber_s; bignumber_s *calc_add(bignumber_s *a, bignumber_s *b); bignumber_s *calc_sub(bignumber_s *a, bignumber_s *b);// 構造大數模板，len指向大數的數據位數，sign表示該大數的符號 bignumber_s *make_bignumber_temp(int len, int sign) {// 分配bignumber_s及其所代表數據 所需的內存bignumber_s *temp = malloc(sizeof(bignumber_s)+len);if (NULL == temp) {perror("Malloc");exit(-1);}temp->sign = sign;temp->len = len;memset(temp->data, 0, len);return temp; }// 處理數字字符串冗余的0，即"00123" -> "123" const char *strip_str(const char *str) {int i = 0;int len = strlen(str);for (i=0; i<len-1&&str[i]=='0'; i++) ;return str+i; } // 將字符串數據填充進模板中 void fill_data_fromstr(bignumber_s *n, const char *str) {int i = 0;int len = n->len;for (i=0; i<len; i++) {int d = str[len-1-i]-'0';if (d>=0 && d<=9) n->data[i] = d;else {fprintf(stderr, "Invalid Number:%s\n", str);exit(-1);}} } // 從字符串構造一個大數 bignumber_s *make_bignumber_fromstr(const char *str) {// 處理負數字符串，即"-123"int sign = 0;if (str[0]=='-') {sign = 1;str++;}// 處理數字字符串冗余的0，即"00123" -> "123"const char * striped_str = strip_str(str);int len = strlen(striped_str);// 指定數據位長度即符號，創建一個大數模板bignumber_s *temp = make_bignumber_temp(len ,sign);// 將字符串數據填充進模板中，完成大數創建fill_data_fromstr(temp, striped_str);return temp; }// 以字符串的形式打印輸出一個大數 void print_bignumber(bignumber_s* b) {int len = b->len;char *str = malloc(len+1);int i = 0;for (i=0; i<len; i++) {str[i] = b->data[len-i-1]+'0';}str[len] = '\0';fprintf(stdout,"%s%s\n", b->sign==1?"-":"", strip_str(str));free(str); }void usage(const char *s) {fprintf(stderr, "Usage:%s number1 +-x/ number2.\n",s);exit(-1); }// 實現無符號加法，a和b為加數，r為和 void add_impl(bignumber_s *a, bignumber_s *b, bignumber_s *r) {int i = 0;char carry = 0;int len = r->len;for (i=0; i<len; i++) {if (i<a->len)carry += a->data[i];if (i<b->len)carry += b->data[i];r->data[i] = carry%BASE;carry /= BASE;} }bignumber_s *calc_add(bignumber_s *a, bignumber_s *b) {// 情況一和情況四if (a->sign==b->sign) {// n位數+m位數，其和最大為max(n,m)+1位數int len = MAX(a->len, b->len) + 1;bignumber_s *result = make_bignumber_temp(len,a->sign);add_impl(a,b,result);return result;} else if (a->sign == 0 && b->sign == 1) {//情況二b->sign = 0; //b數去絕對值return calc_sub(a,b);} else if (a->sign == 1 && b->sign == 0) {//情況三a->sign = 0; //a數去絕對值return calc_sub(b,a);} }// 實現無符號減法，a-b , r為差 void sub_impl(bignumber_s *a, bignumber_s *b, bignumber_s *r) {int i=0;int borrow = 0;int len = r->len;int temp = 0;for (i=0; i<len; i++) {temp = a->data[i]+BASE-borrow-((i<b->len)?b->data[i]:0);r->data[i] = temp%BASE;borrow = temp/BASE?0:1;} }int valid_len(bignumber_s *a) {int len = a->len;int i = len-1;for (i=len-1; i>=0; i--) {if (a->data[i]==0) len--;else break;}return len; } // 判斷兩個大數的大小 // a > b 返回1 ，a<b 返回 -1 , a==b 返回0 int cmp(bignumber_s *a, bignumber_s *b) {if (a->sign==0&&b->sign==1) return 1;if (a->sign==1&&b->sign==0) return -1;int sign = a->sign;int alen = valid_len(a);int blen = valid_len(b);if (alen>blen) return (sign==1?-1:1);else if (alen<blen) return (sign==1?1:-1);else {int i = 0;int len = alen;for (i=len-1; i>=0; i--) {if (a->data[i]>b->data[i])return (sign==1?-1:1);else if (a->data[i]<b->data[i]) return (sign==1?1:-1);}return 0;} }bignumber_s *calc_sub(bignumber_s *a, bignumber_s *b) {// 情況一if(a->sign==0 && b->sign==0) {if (cmp(a,b)>=0) { // 被減數大于等于減數，即差大于等于0時int len = a->len;bignumber_s *result = make_bignumber_temp(len,0);sub_impl(a,b,result);return result;} else { // 被減數小于減數，即差小于0時int len = b->len;bignumber_s *result = make_bignumber_temp(len,1);sub_impl(b,a,result);return result;}} else if (a->sign==1 && b->sign==1) { //情況四b->sign=0; a->sign=0;return calc_sub(b,a); //調換減數和被減數，變成情況一}else if (a->sign==0 && b->sign==1) { // 情況二b->sign=0;bignumber_s *result = calc_add(a,b);result->sign = 0;return result; } else if (a->sign==1 && b->sign==0) { // 情況三a->sign=0;bignumber_s *result = calc_add(a,b);result->sign = 1;return result; } }bignumber_s *calc_mul(bignumber_s *a, bignumber_s *b) {// 實現乘法return NULL; } bignumber_s *calc_div(bignumber_s *a, bignumber_s *b) {// 實現除法return NULL; } int main(int argc, char *argv[]) {bignumber_s *a = make_bignumber_fromstr(argv[1]);bignumber_s *b = make_bignumber_fromstr(argv[3]);if (argc!=4) usage(argv[0]);if (0 == strcmp(argv[2],"+"))print_bignumber(calc_add(a,b));else if (0 == strcmp(argv[2],"-"))print_bignumber(calc_sub(a,b));else if (0 == strcmp(argv[2],"x"))print_bignumber(calc_mul(a,b));else if (0 == strcmp(argv[2],"/"))print_bignumber(calc_div(a,b));else usage(argv[0]);return 0; }

2.4.4 演示

編譯命令：

$ gcc -o calculatorv2 calculatorv2.c

結果演示：

2.5 實現乘法

2.5.1 正數乘法實現

乘法的實現稍微比加減法復雜一些，但是和加減法是同樣的實現原理。

依舊搬出我們的豎式計算法：

假設x[0...n]乘以y[0...m]，其中0代表x數的個位，n代表x數的最高位，假設用x代表上述的145這個數。那么x[0]就是5， x[1]就是4， x[1]就是1； 類似的y代表12， 則y[0]為2， y[1]為1。

乘法的實現思路：

x與y的積，位數為n+m，即積為z[0...n+m]

先用y的每個位去乘以x，如上述例子先用2乘以145，再用1乘以145， 從而得出對應于y每個位的積。

再將步驟2計算出來的所有積，按其基數累加到積中。

這里有兩點需要注意：

y[i]乘以x[j]時，其積應在z[i+j]。

y[i]乘以x[0...n]其積，應累加到z[i...m+n]中

代碼實現如下：

void mul_impl(bignumber_s *x, bignumber_s *y, bignumber_s *z) {int n = x->len;int m = y->len;int i = 0;int j = 0;int carry = 0;for (i=0; i<m; i++) {// y的每一位乘以x，即計算y[i] * x[0...n] 并累加到z[i...i+n]中for (j=0; j<n; j++) {carry += y->data[i]*x->data[j] + z->data[i+j];z->data[i+j] = carry%BASE;carry /= BASE;}// 將剩余的進位,繼續在z[i+n...n+m]中累加，從而完成y[i]乘以x[0...n]其積累加到z[i...m+n]中for (; j+i<n+m; j++) {carry += z->data[i+j];z->data[i+j] = carry % BASE;carry /= BASE;}} }bignumber_s *calc_mul(bignumber_s *a, bignumber_s *b) {int len = a->len + b->len;bignumber_s *result = make_bignumber_temp(len,0);mul_impl(a,b,result);return result; }

2.5.2 有符號乘法

有符號的 乘法可以轉化為無符號的乘法，分以下兩種情況：

// 情況一 (A>0 && B>0) 或者 (A>0 && B>0) A x B --> |A| x |B| // 情況二 (A>0 && B<0) 或者 (A<0 && B>0) A x B --> -(|A| x |B|)

代碼實現如下：

bignumber_s *calc_mul(bignumber_s *a, bignumber_s *b) {int len = a->len + b->len;bignumber_s *result = make_bignumber_temp(len,a->sign==b->sign?0:1); //a->sign==b->sign為情況一，否則為情況二。mul_impl(a,b,result);return result; }

2.5.3大數計算器v3版本

/* * file name : calculatorv3.c * desp : calculator version 3 */ #include <stdio.h> #include <stdlib.h> #include <string.h>#define BASE (10) #define MAX(x,y) ((x)>(y)?(x):(y))// 大數數據結構 typedef struct bignumber_s{char sign; // 代表大數的符號，1為負數，0為正數int len; // 代表大數的位數char data[]; // 大數的數據內容，data[0]代表個位，data[1]代表十位，data[2]代表百位.... } bignumber_s;bignumber_s *calc_add(bignumber_s *a, bignumber_s *b); bignumber_s *calc_sub(bignumber_s *a, bignumber_s *b);// 構造大數模板，len指向大數的數據位數，sign表示該大數的符號 bignumber_s *make_bignumber_temp(int len, int sign) {// 分配bignumber_s及其所代表數據 所需的內存bignumber_s *temp = malloc(sizeof(bignumber_s)+len);if (NULL == temp) {perror("Malloc");exit(-1);}temp->sign = sign;temp->len = len;memset(temp->data, 0, len);return temp; }// 處理數字字符串冗余的0，即"00123" -> "123" const char *strip_str(const char *str) {int i = 0;int len = strlen(str);for (i=0; i<len-1&&str[i]=='0'; i++) ;return str+i; } // 將字符串數據填充進模板中 void fill_data_fromstr(bignumber_s *n, const char *str) {int i = 0;int len = n->len;for (i=0; i<len; i++) {int d = str[len-1-i]-'0';if (d>=0 && d<=9) n->data[i] = d;else {fprintf(stderr, "Invalid Number:%s\n", str);exit(-1);}} } // 從字符串構造一個大數 bignumber_s *make_bignumber_fromstr(const char *str) {// 處理負數字符串，即"-123"int sign = 0;if (str[0]=='-') {sign = 1;str++;}// 處理數字字符串冗余的0，即"00123" -> "123"const char * striped_str = strip_str(str);int len = strlen(striped_str);// 指定數據位長度即符號，創建一個大數模板bignumber_s *temp = make_bignumber_temp(len ,sign);// 將字符串數據填充進模板中，完成大數創建fill_data_fromstr(temp, striped_str);return temp; }// 以字符串的形式打印輸出一個大數 void print_bignumber(bignumber_s* b) {int len = b->len;char *str = malloc(len+1);int i = 0;for (i=0; i<len; i++) {str[i] = b->data[len-i-1]+'0';}str[len] = '\0';fprintf(stdout,"%s%s\n", b->sign==1?"-":"", strip_str(str));free(str); }void usage(const char *s) {fprintf(stderr, "Usage:%s number1 +-x/ number2.\n",s);exit(-1); }// 實現無符號加法，a和b為加數，r為和 void add_impl(bignumber_s *a, bignumber_s *b, bignumber_s *r) {int i = 0;char carry = 0;int len = r->len;for (i=0; i<len; i++) {if (i<a->len)carry += a->data[i];if (i<b->len)carry += b->data[i];r->data[i] = carry%BASE;carry /= BASE;} }bignumber_s *calc_add(bignumber_s *a, bignumber_s *b) {// 情況一和情況四if (a->sign==b->sign) {// n位數+m位數，其和最大為max(n,m)+1位數int len = MAX(a->len, b->len) + 1;bignumber_s *result = make_bignumber_temp(len,a->sign);add_impl(a,b,result);return result;} else if (a->sign == 0 && b->sign == 1) {//情況二b->sign = 0; //b數去絕對值return calc_sub(a,b);} else if (a->sign == 1 && b->sign == 0) {//情況三a->sign = 0; //a數去絕對值return calc_sub(b,a);} }// 實現無符號減法，a-b , r為差 void sub_impl(bignumber_s *a, bignumber_s *b, bignumber_s *r) {int i=0;int borrow = 0;int len = r->len;int temp = 0;for (i=0; i<len; i++) {temp = a->data[i]+BASE-borrow-((i<b->len)?b->data[i]:0);r->data[i] = temp%BASE;borrow = temp/BASE?0:1;} }int valid_len(bignumber_s *a) {int len = a->len;int i = len-1;for (i=len-1; i>=0; i--) {if (a->data[i]==0) len--;else break;}return len; } // 判斷兩個大數的大小 // a > b 返回1 ，a<b 返回 -1 , a==b 返回0 int cmp(bignumber_s *a, bignumber_s *b) {if (a->sign==0&&b->sign==1) return 1;if (a->sign==1&&b->sign==0) return -1;int sign = a->sign;int alen = valid_len(a);int blen = valid_len(b);if (alen>blen) return (sign==1?-1:1);else if (alen<blen) return (sign==1?1:-1);else {int i = 0;int len = alen;for (i=len-1; i>=0; i--) {if (a->data[i]>b->data[i])return (sign==1?-1:1);else if (a->data[i]<b->data[i]) return (sign==1?1:-1);}return 0;} }bignumber_s *calc_sub(bignumber_s *a, bignumber_s *b) {// 情況一if(a->sign==0 && b->sign==0) {if (cmp(a,b)>=0) { // 被減數大于等于減數，即差大于等于0時int len = a->len;bignumber_s *result = make_bignumber_temp(len,0);sub_impl(a,b,result);return result;} else { // 被減數小于減數，即差小于0時int len = b->len;bignumber_s *result = make_bignumber_temp(len,1);sub_impl(b,a,result);return result;}} else if (a->sign==1 && b->sign==1) { //情況四b->sign=0; a->sign=0;return calc_sub(b,a); //調換減數和被減數，變成情況一}else if (a->sign==0 && b->sign==1) { // 情況二b->sign=0;bignumber_s *result = calc_add(a,b);result->sign = 0;return result; } else if (a->sign==1 && b->sign==0) { // 情況三a->sign=0;bignumber_s *result = calc_add(a,b);result->sign = 1;return result; } }// 實現無符號乘法，axb , z為積 void mul_impl(bignumber_s *x, bignumber_s *y, bignumber_s *z) {int n = x->len;int m = y->len;int i = 0;int j = 0;int carry = 0;for (i=0; i<m; i++) {// y的每一位乘以x，即計算y[i] * x[0...n] 并累加到z[i...i+n]中for (j=0; j<n; j++) {carry += y->data[i]*x->data[j] + z->data[i+j];z->data[i+j] = carry%BASE;carry /= BASE;}// 將剩余的進位,繼續在z[i+n...n+m]中累加，從而完成y[i]乘以x[0...n]其積累加到z[i...m+n]中for (; j+i<n+m; j++) {carry += z->data[i+j];z->data[i+j] = carry % BASE;carry /= BASE;}} }bignumber_s *calc_mul(bignumber_s *a, bignumber_s *b) {int len = a->len + b->len;bignumber_s *result = make_bignumber_temp(len,a->sign==b->sign?0:1); //a->sign==b->sign為情況一，否則為情況二。mul_impl(a,b,result);return result; }bignumber_s *calc_div(bignumber_s *a, bignumber_s *b) {// 實現除法return NULL; } int main(int argc, char *argv[]) {bignumber_s *a = make_bignumber_fromstr(argv[1]);bignumber_s *b = make_bignumber_fromstr(argv[3]);if (argc!=4) usage(argv[0]);if (0 == strcmp(argv[2],"+"))print_bignumber(calc_add(a,b));else if (0 == strcmp(argv[2],"-"))print_bignumber(calc_sub(a,b));else if (0 == strcmp(argv[2],"x"))print_bignumber(calc_mul(a,b));else if (0 == strcmp(argv[2],"/"))print_bignumber(calc_div(a,b));else usage(argv[0]);return 0; }

2.5.4 演示

編譯命令：

$ gcc -o calculatorv3 calculatorv3.c

結果演示：

2.6 實現除法

2.6.1 除法實現

除法的實現，我們直接轉化為減法，大致思路如下：

用被除數減去除數，

差大于等于0時，商的值加1，將差賦值給被除數，重新回到步驟1

差小于0時，整個除法計算過程完畢。

這種實現方法，在某種情況下效率會非常低，但是實現起來比較簡單。

有符號的除法，其處理更乘法是一致的。

除法實現代碼如下：

// 大數加一操作 void plusone(bignumber_s *a) {int len = a->len ;int i;int carry = 1;for (i=0; i<len; i++) {carry += a->data[i];a->data[i] = carry%BASE;carry /= BASE;} } // 大數除法實現 bignumber_s *calc_div(bignumber_s *a, bignumber_s *b) {bignumber_s *zero = make_bignumber_temp(1,0);if (cmp(b,zero)==0) {// 除數為0 報錯fprintf(stderr,"Integer division by zero\n");exit(-1);}else if (cmp(a,zero)==0) { // 被除數為0 ，結果為0return zero;}int len = a->len;bignumber_s *result = make_bignumber_temp(len,a->sign==b->sign?0:1);a->sign = 0;b->sign = 0;bignumber_s *temp = make_bignumber_temp(len, 0);bignumber_s *aa = a;while(1) {if (cmp(aa, b)>=0) {sub_impl(aa, b, temp);plusone(result);aa = temp;} else {free(temp);return result;}} }

2.6.2 大數計算器v4版本

/* * file name : calculatorv4.c * desp : calculator version 4 */ #include <stdio.h> #include <stdlib.h> #include <string.h>#define BASE (10) #define MAX(x,y) ((x)>(y)?(x):(y))// 大數數據結構 typedef struct bignumber_s{char sign; // 代表大數的符號，1為負數，0為正數int len; // 代表大數的位數char data[]; // 大數的數據內容，data[0]代表個位，data[1]代表十位，data[2]代表百位.... } bignumber_s;bignumber_s *calc_add(bignumber_s *a, bignumber_s *b); bignumber_s *calc_sub(bignumber_s *a, bignumber_s *b);// 構造大數模板，len指向大數的數據位數，sign表示該大數的符號 bignumber_s *make_bignumber_temp(int len, int sign) {// 分配bignumber_s及其所代表數據 所需的內存bignumber_s *temp = malloc(sizeof(bignumber_s)+len);if (NULL == temp) {perror("Malloc");exit(-1);}temp->sign = sign;temp->len = len;memset(temp->data, 0, len);return temp; }// 處理數字字符串冗余的0，即"00123" -> "123" const char *strip_str(const char *str) {int i = 0;int len = strlen(str);for (i=0; i<len-1&&str[i]=='0'; i++) ;return str+i; } // 將字符串數據填充進模板中 void fill_data_fromstr(bignumber_s *n, const char *str) {int i = 0;int len = n->len;for (i=0; i<len; i++) {int d = str[len-1-i]-'0';if (d>=0 && d<=9) n->data[i] = d;else {fprintf(stderr, "Invalid Number:%s\n", str);exit(-1);}} } // 從字符串構造一個大數 bignumber_s *make_bignumber_fromstr(const char *str) {// 處理負數字符串，即"-123"int sign = 0;if (str[0]=='-') {sign = 1;str++;}// 處理數字字符串冗余的0，即"00123" -> "123"const char * striped_str = strip_str(str);int len = strlen(striped_str);// 指定數據位長度即符號，創建一個大數模板bignumber_s *temp = make_bignumber_temp(len ,sign);// 將字符串數據填充進模板中，完成大數創建fill_data_fromstr(temp, striped_str);return temp; }// 以字符串的形式打印輸出一個大數 void print_bignumber(bignumber_s* b) {int len = b->len;char *str = malloc(len+1);int i = 0;for (i=0; i<len; i++) {str[i] = b->data[len-i-1]+'0';}str[len] = '\0';fprintf(stdout,"%s%s\n", b->sign==1?"-":"", strip_str(str));free(str); }void usage(const char *s) {fprintf(stderr, "Usage:%s number1 +-x/ number2.\n",s);exit(-1); }// 實現無符號加法，a和b為加數，r為和 void add_impl(bignumber_s *a, bignumber_s *b, bignumber_s *r) {int i = 0;char carry = 0;int len = r->len;for (i=0; i<len; i++) {if (i<a->len)carry += a->data[i];if (i<b->len)carry += b->data[i];r->data[i] = carry%BASE;carry /= BASE;} }bignumber_s *calc_add(bignumber_s *a, bignumber_s *b) {// 情況一和情況四if (a->sign==b->sign) {// n位數+m位數，其和最大為max(n,m)+1位數int len = MAX(a->len, b->len) + 1;bignumber_s *result = make_bignumber_temp(len,a->sign);add_impl(a,b,result);return result;} else if (a->sign == 0 && b->sign == 1) {//情況二b->sign = 0; //b數去絕對值return calc_sub(a,b);} else if (a->sign == 1 && b->sign == 0) {//情況三a->sign = 0; //a數去絕對值return calc_sub(b,a);} }// 實現無符號減法，a-b , r為差 void sub_impl(bignumber_s *a, bignumber_s *b, bignumber_s *r) {int i=0;int borrow = 0;int len = r->len;int temp = 0;for (i=0; i<len; i++) {temp = a->data[i]+BASE-borrow-((i<b->len)?b->data[i]:0);r->data[i] = temp%BASE;borrow = temp/BASE?0:1;} }int valid_len(bignumber_s *a) {int len = a->len;int i = len-1;for (i=len-1; i>=0; i--) {if (a->data[i]==0) len--;else break;}return len; } // 判斷兩個大數的大小 // a > b 返回1 ，a<b 返回 -1 , a==b 返回0 int cmp(bignumber_s *a, bignumber_s *b) {if (a->sign==0&&b->sign==1) return 1;if (a->sign==1&&b->sign==0) return -1;int sign = a->sign;int alen = valid_len(a);int blen = valid_len(b);if (alen>blen) return (sign==1?-1:1);else if (alen<blen) return (sign==1?1:-1);else {int i = 0;int len = alen;for (i=len-1; i>=0; i--) {if (a->data[i]>b->data[i])return (sign==1?-1:1);else if (a->data[i]<b->data[i]) return (sign==1?1:-1);}return 0;} }bignumber_s *calc_sub(bignumber_s *a, bignumber_s *b) {// 情況一if(a->sign==0 && b->sign==0) {if (cmp(a,b)>=0) { // 被減數大于等于減數，即差大于等于0時int len = a->len;bignumber_s *result = make_bignumber_temp(len,0);sub_impl(a,b,result);return result;} else { // 被減數小于減數，即差小于0時int len = b->len;bignumber_s *result = make_bignumber_temp(len,1);sub_impl(b,a,result);return result;}} else if (a->sign==1 && b->sign==1) { //情況四b->sign=0; a->sign=0;return calc_sub(b,a); //調換減數和被減數，變成情況一}else if (a->sign==0 && b->sign==1) { // 情況二b->sign=0;bignumber_s *result = calc_add(a,b);result->sign = 0;return result; } else if (a->sign==1 && b->sign==0) { // 情況三a->sign=0;bignumber_s *result = calc_add(a,b);result->sign = 1;return result; } }// 實現無符號乘法，x * y , z為積 void mul_impl(bignumber_s *x, bignumber_s *y, bignumber_s *z) {int n = x->len;int m = y->len;int i = 0;int j = 0;int carry = 0;for (i=0; i<m; i++) {// y的每一位乘以x，即計算y[i] * x[0...n] 并累加到z[i...i+n]中for (j=0; j<n; j++) {carry += y->data[i]*x->data[j] + z->data[i+j];z->data[i+j] = carry%BASE;carry /= BASE;}// 將剩余的進位,繼續在z[i+n...n+m]中累加，從而完成y[i]乘以x[0...n]其積累加到z[i...m+n]中for (; j+i<n+m; j++) {carry += z->data[i+j];z->data[i+j] = carry % BASE;carry /= BASE;}} }bignumber_s *calc_mul(bignumber_s *a, bignumber_s *b) {int len = a->len + b->len;bignumber_s *result = make_bignumber_temp(len,a->sign==b->sign?0:1); //a->sign==b->sign為情況一，否則為情況二。mul_impl(a,b,result);return result; }// 大數加一操作 void plusone(bignumber_s *a) {int len = a->len ;int i;int carry = 1;for (i=0; i<len; i++) {carry += a->data[i];a->data[i] = carry%BASE;carry /= BASE;} } // 大數除法實現 bignumber_s *calc_div(bignumber_s *a, bignumber_s *b) {bignumber_s *zero = make_bignumber_temp(1,0);if (cmp(b,zero)==0) {// 除數為0 報錯fprintf(stderr,"Integer division by zero\n");exit(-1);}else if (cmp(a,zero)==0) { // 被除數為0 ，結果為0return zero;}int len = a->len;bignumber_s *result = make_bignumber_temp(len,a->sign==b->sign?0:1);a->sign = 0;b->sign = 0;bignumber_s *temp = make_bignumber_temp(len, 0);bignumber_s *aa = a;while(1) {if (cmp(aa, b)>=0) {sub_impl(aa, b, temp);plusone(result);aa = temp;} else {free(temp);return result;}} }int main(int argc, char *argv[]) {bignumber_s *a = make_bignumber_fromstr(argv[1]);bignumber_s *b = make_bignumber_fromstr(argv[3]);if (argc!=4) usage(argv[0]);if (0 == strcmp(argv[2],"+"))print_bignumber(calc_add(a,b));else if (0 == strcmp(argv[2],"-"))print_bignumber(calc_sub(a,b));else if (0 == strcmp(argv[2],"x"))print_bignumber(calc_mul(a,b));else if (0 == strcmp(argv[2],"/"))print_bignumber(calc_div(a,b));else usage(argv[0]);return 0; }

2.6.3 演示

編譯命令：

$ gcc -o calculatorv4 calculatorv4.c

結果演示：

大數計算器在解決除法問題的時候僅實現了商的求解，并未對余數進行過多的處理，其實這是不完善的。大家可以在此基礎上，思考思考如何改進能夠讓計算器更加完善。

三、實驗總結

本實驗通過完成一個大數計算器的玩具程序，一方面有助于理解計算機數學運算的實現機理，另一方面有助于提升c語言的編程能力。 當然我們的大數計算器，在除法方面的性能還是不太令人滿意的，希望有興趣的讀者朋友，后續能夠對計算器實現進行改進。

四、參考鏈接

• C語言接口與實現

總結

以上是生活随笔為你收集整理的C语言实现大数计算器的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。