程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> 關於C語言 >> 一步一步寫算法(之大數計算)

一步一步寫算法(之大數計算)

編輯:關於C語言

 

【 聲明:版權所有,歡迎轉載,請勿用於商業用途。  聯系信箱:feixiaoxing @163.com】

 

 

 

 

    我們知道在x86的32位cpu上面,int表示32位,如果核算成整數的話,大約是40多億。同樣,如果在64位cpu上面,能表示的最大整數就是64位二進制,表示的數值要大得多。那麼在32位如果想表示大整數怎麼辦呢?那只能靠我們自己想辦法了。

 

    首先我們回顧一下我們手算整數的加減、乘除法是怎麼做到的:

 

    (1)記住9*9之間的乘法口訣

 

    (2)記住個位與個位之間的加減法

 

    (3)所有乘法用加法和左移位表示,所有的減法用減法和右移位表示

 

    明白上面的道理之後,我們就可以自己手動寫一個大整數的加法了:

 

 

int* big_int_add(int src1[], int length1, int src2[], int length2) 

    int* dest = NULL; 

    int length; 

    int index; 

    int smaller; 

    int prefix = 0; 

 

    if(NULL == src1 || 0 >= length1 || NULL == src2 || 0 >= length2) 

        return NULL; 

 

    length = length1 > length2 ? (length1 + 1) : (length2 + 1); 

    dest = (int*)malloc(sizeof(int) * length); 

    assert(NULL != dest); 

    memset(dest, 0, sizeof(int) * length); 

 

    smaller = (length2 < length1) ? length2 : length1; 

    for(index = 0; index < smaller; index ++) 

        dest[index] = src1[index] + src2[index]; 

 

    if(length1 > length2){ 

        for(; index < length1; index++) 

            dest[index] = src1[index]; 

    }else{ 

        for(; index < length2; index++) 

            dest[index] = src2[index]; 

    } 

 

    for(index = 0; index < length; index ++){ 

        dest[index] += prefix;  

        prefix = dest[index] / 10; 

        dest[index] %= 10; 

    } 

 

    return dest; 

int* big_int_add(int src1[], int length1, int src2[], int length2)

{

       int* dest = NULL;

       int length;

       int index;

       int smaller;

       int prefix = 0;

 

       if(NULL == src1 || 0 >= length1 || NULL == src2 || 0 >= length2)

              return NULL;

 

       length = length1 > length2 ? (length1 + 1) : (length2 + 1);

       dest = (int*)malloc(sizeof(int) * length);

       assert(NULL != dest);

       memset(dest, 0, sizeof(int) * length);

 

       smaller = (length2 < length1) ? length2 : length1;

       for(index = 0; index < smaller; index ++)

              dest[index] = src1[index] + src2[index];

 

       if(length1 > length2){

              for(; index < length1; index++)

                     dest[index] = src1[index];

       }else{

              for(; index < length2; index++)

                     dest[index] = src2[index];

       }

 

       for(index = 0; index < length; index ++){

              dest[index] += prefix;

              prefix = dest[index] / 10;

              dest[index] %= 10;

       }

 

       return dest;

}    上面算法最大的特點就是:計算的時候沒有考慮10進制,等到所有結果出來之後開始對每一位進行進制處理。

 

 

 

 

討論:

 

    看到上面的算法之後,大家可以考慮一下:

 

    (1)減法應該怎麼寫呢?

 

    (2)乘法呢?除法呢?

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved