華為 OJ 大整數乘法：兩種 C 語言實現方案詳解（模擬筆算法 vs 免進位累加法）

題目要求

輸入兩個不超過 100 位的大整數，輸出它們的乘積。樣例：1234567 123 → 151851741。OJ 提交需去除調試輸出。

方法一：模擬手工豎式乘法

核心邏輯

1. 字符串存儲大整數 num1、num2
2. 外層循環遍歷 num2 每一位 (從低位到高位)
3. 內層循環 num1 每位相乘 + 進位，結果存入臨時數組 tempRes
4. 將 tempRes 與總結果 result 對齊相加 (每輪左偏移一位)，處理進位

關鍵代碼片段

// 計算 num1 × num2[j] 存入 tempRes
for (i = num1Len-1; i >= 0; i--) {
    res = Int(num1[i]) * Int(num2[j]) + carry;
    tempRes[tempResLen--] = Char(res % 10);
    carry = res / 10;
}
tempRes[tempResLen] = Char(carry); // 最高位進位

// tempRes 與 result 累加 (右對齊，每輪左偏移)
for (k = resultLen-offset; k > resultLen-offset-num1Len; k--) {
    res = Int(result[k]) + Int(tempRes[tempResLen--]) + carry;
    result[k] = Char(res % 10);
    carry = res / 10;
}
result[k] += Int(tempRes[tempResLen] + carry);

宏定義技巧：#define Int(X) (X-'0')、#define Char(X) (X+'0') 實現字符/數字快速轉換。

方法二：免進位累加後統一處理進位（更優雅）

核心洞察

乘法本質是各位乘積按權重累加。可先忽略進位，將所有 num1[i] × num2[j] 直接累加到 result[i+j] 對應位置，最後從低位向高位統一處理進位。

算法步驟

1. 結果數組 result 類型必須為 int (而非 char)，因單位最大累加值 100×9×9=8100 超出 char 范圍
2. 雙層循環累加：result[i+j+2] += Int(num1[i]) * Int(num2[j]) (前兩位保留長度與最終進位)
3. 統一進位處理：從末位向首位，result[i-1] += result[i]/10; result[i] %= 10
4. 輸出時跳過前導零

核心代碼

// 免進位累加
for (j = 0; j < num2Len; j++)
    for (i = 0; i < num1Len; i++)
        result[i+j+2] += Int(num1[i]) * Int(num2[j]);

// 統一進位
for (i = resultLen; i > 1; i--) {
    result[i-1] += result[i] / 10;
    result[i] %= 10;
}

兩種方案對比

工程落地建議

• 競賽/面試推薦方法二：代碼短、邊界少、易驗證
• 生產級大整數庫建議封裝為結構體，實現完整四則運算、比較、導入導出
• 注意輸入合法性檢查：長度限制、非數字字符、符號位處理