您现在的位置：程式碼之家 >> 編程語言 > >> C語言 >> C >> 關於C

C語言極簡實作：大數乘法最短程式碼

編輯：關於C

196 位元組極限挑戰：遞迴實作大數乘法

這是一個追求極致程式碼長度的「高爾夫球式程式設計」作品，僅 196 字元（GCC 下）實作任意長度整數乘法。僅供欣賞與學習技巧，嚴禁用於生產環境。

極簡版程式碼（GCC 可編譯）

#include <stdio.h>
char s[99],t[99];int m,n;void r(int i,int c){int j=0,k=i;while(k)c+=s[j++]*t[k---1];if(i)r(i-1,c/10);printf("%d",c%10);}void main(){gets(s);gets(t);while(s[n])s[n++]-=48;while(t[m])t[m++]-=48;r(m+n-1,0);}

可讀性重構版

#include <stdio.h>

char s[99], t[99];  // 輸入緩衝區（儲存字符）
int m, n;           // 兩數長度

// 遞迴計算第 i 位結果（從低位到高位）
void multiply_recursive(int pos, int carry) {
    int j = 0, k = pos;
    int sum = carry;
    
    // 手動模擬乘法：Σ s[j] * t[k-j]
    while (k >= 0) {
        sum += s[j] * t[k];
        j++; k--;
    }
    
    if (pos > 0) 
        multiply_recursive(pos - 1, sum / 10); // 處理高位，傳遞進位
    
    putchar('0' + (sum % 10)); // 輸出當前位
}

int main() {
    gets(s); gets(t); // 讀取兩數字串
    
    // 字符轉數值 (ASCII '0'=48)
    while (s[n]) s[n++] -= '0';
    while (t[m]) t[m++] -= '0';
    
    multiply_recursive(m + n - 2, 0); // 最高位索引 = 總長度-2
    return 0;
}

核心演算法解析

輸入處理：讀取字串，逐字符減去 '0' 轉為數值陣列
遞迴乘法：模擬手算豎式乘法，pos 代表結果陣列索引（從高位遞迴到低位）
進位傳遞：遞迴返回時由高位向低位傳遞進位，利用呼叫棧天然儲存中間狀態
輸出順序：遞迴最深處先輸出高位，回溯時依序輸出低位，順序正確

極簡技巧總結

技巧	說明	代價
全域變數	免參數傳遞、自動歸零	不可重入、執行緒不安全
遞迴替代迴圈	省去迴圈變數、利用棧儲狀態	棧溢位風險、效能較差
條件簡化	`if(i)` 替代 `if(i>0)`	可讀性極差
運算符副作用	`k---1` 合併遞減與判斷	極難維護
省略標準頭部	GCC 隱含 int、隱含函數宣告	不符標準、現代編譯器報錯

作者原話警語

「在實際工作中，千萬不要寫這樣的程序，否則會被罵死。不要用這個程序考你的學生和面試者，即使他宣稱精通 C 語言。」

正規大數乘法參考實作

// 生產級：迭代 + 動態記憶體 + 完整錯誤處理
void multiply_bigint(const char *a, const char *b, char *result, int max_len) {
    int len_a = strlen(a), len_b = strlen(b);
    int *prod = calloc(len_a + len_b, sizeof(int));
    
    for (int i = len_a - 1; i >= 0; i--)
        for (int j = len_b - 1; j >= 0; j--)
            prod[i + j + 1] += (a[i]-'0') * (b[j]-'0');
    
    for (int i = len_a + len_b - 1; i > 0; i--) {
        prod[i-1] += prod[i] / 10;
        prod[i] %= 10;
    }
    
    // 轉字串輸出...
    free(prod);
}