C 語言大整數加法完整實現：分塊十進制數組模擬豎式運算

問題背景

需讀入兩個超長整數 (超過 long long 範圍)，以字符串存儲，實現精確加法並輸出結果。標準類型無法容納，必須自定義大整數結構與運算。

核心設計：基數 10^9 分塊存儲

• 每個 int 元素存儲 **9 位十進制數字** (基數 BASE = 1,000,000,000)；
• 利用 32 位有符號整數範圍 (2,147,483,647) 安全容納基數及進位；
• 低位在數組低索引 (小端序)，便於進位傳遞。

完整代碼實現 (含詳細註釋)

#include 
#include 
#include 

#define BASE 1000000000      // 10^9
#define MAX_DIGITS 100       // 最大塊數，支持 ~900 位十進制數
#define POSITIVE 1
#define NEGATIVE -1

typedef struct {
    int digits[MAX_DIGITS];  // 低位在前
    int length;              // 有效塊數
    int sign;                // 正負號
} BigInt;

// 字符串 → BigInt
void strToBigInt(const char* s, BigInt* n) {
    memset(n, 0, sizeof(BigInt));
    if (s[0] == '-') { n->sign = NEGATIVE; s++; }
    else n->sign = POSITIVE;
    
    int len = strlen(s);
    for (int i = len; i > 0; i -= 9) {
        int start = (i >= 9) ? i - 9 : 0;
        int chunkLen = i - start;
        char buf[10] = {0};
        strncpy(buf, s + start, chunkLen);
        n->digits[n->length++] = atoi(buf);
    }
    // 去除前導零塊
    while (n->length > 1 && n->digits[n->length - 1] == 0) n->length--;
}

// BigInt 加法 (同號相加，異號轉減法)
void addBigInt(const BigInt* a, const BigInt* b, BigInt* res) {
    memset(res, 0, sizeof(BigInt));
    if (a->sign == b->sign) {
        res->sign = a->sign;
        int carry = 0;
        int maxLen = (a->length > b->length) ? a->length : b->length;
        for (int i = 0; i < maxLen || carry; i++) {
            long long sum = carry;
            if (i < a->length) sum += a->digits[i];
            if (i < b->length) sum += b->digits[i];
            res->digits[res->length++] = (int)(sum % BASE);
            carry = (int)(sum / BASE);
        }
    } else {
        // 異號：調用減法 (此處省略，完整代碼需實現 cmpAbs, subBigInt)
        // 為演示簡化，假設同號
    }
}

// 輸出 BigInt
void printBigInt(const BigInt* n) {
    if (n->sign == NEGATIVE) putchar('-');
    printf("%d", n->digits[n->length - 1]); // 最高塊不補零
    for (int i = n->length - 2; i >= 0; i--) {
        printf("%09d", n->digits[i]); // 低位塊補零到 9 位
    }
}

int main() {
    char s1[1000], s2[1000];
    printf("輸入第一個大整數: "); scanf("%s", s1);
    printf("輸入第二個大整數: "); scanf("%s", s2);
    
    BigInt a, b, res;
    strToBigInt(s1, &a);
    strToBigInt(s2, &b);
    addBigInt(&a, &b, &res);
    
    printf("和 = "); printBigInt(&res); putchar('\n');
    return 0;
}

關鍵算法細節

擴展功能建議

• 減法/乘法/除法：模擬豎式算法，乘法用雙重循環累加，除法用試商法；
• 輸入驗證：正則 ^-?\d+$ 檢查字符串合法性；
• 動態內存：malloc/realloc 替換固定數組，支持任意長度；
• 基數優化：64 位環境可用 BASE = 10^18 (用 unsigned long long)，減少塊數提升性能；
• 庫替代：生產環境直接用 GMP (GNU Multiple Precision)：mpz_t 類型、mpz_add 等，經過工業級驗證。

總結

C 語言大整數加法核心在於 **基數分塊存儲 + 模擬豎式進位**。選擇 BASE=10^9 平衡了 32 位整數安全性與存儲效率。完整代碼包含字符串解析、加法邏輯、格式化輸出三大模塊，可直接編譯運行。工程實踐中優先考慮 GMP 庫，自行實現僅作教學或極簡依賴場景。