高精度運算核心概念

高精度運算處理超出標準資料型別（int、long long）表示範圍的數值運算。例如計算兩個 200 位數的和，標準型別無法容納，必須採用陣列模擬人工豎式計算。

演算法核心邏輯

1. 資料表示：字元陣列儲存輸入，轉換為整數陣列，個位數對應索引 0（或 1），便於進位處理
2. 對齊相加：從低位向高位逐位相加，對應人工豎式「個位對個位、十位對十位」
3. 進位處理：當前位總和 = 對應位數字相加 + 來自低位的進位；當前位結果 = 總和 % 10；新進位 = 總和 / 10
4. 最高位進位：最高位運算後若仍有進位，需擴展結果陣列

關鍵實作細節

ASCII 碼轉換

char input[] = "12345";
int digits[100];
for (int i = 0; i < strlen(input); ++i) {
    digits[len - 1 - i] = input[i] - '0';  // '0' ASCII = 48，字元轉數值
}
// digits[0] = 5 (個位), digits[1] = 4 (十位)...

核心加法迴圈

int carry = 0;
int idx = 0;
while (idx < lenA || idx < lenB) {
    int sum = a[idx] + b[idx] + carry;  // 缺位視為 0
    result[idx] = sum % 10;             // 當前位
    carry = sum / 10;                   // 進位
    ++idx;
}
if (carry > 0) result[idx++] = carry;   // 最高位進位

完整可執行程式碼

#include <iostream>
#include <cstring>
#include <string>
#include <algorithm>

using namespace std;

string addLargeNumbers(const string& num1, const string& num2) {
    // 處理空字串
    if (num1.empty()) return num2;
    if (num2.empty()) return num1;

    string result;
    result.reserve(max(num1.size(), num2.size()) + 1);

    int carry = 0;
    int i = num1.size() - 1;
    int j = num2.size() - 1;

    // 從低位向高位處理
    while (i >= 0 || j >= 0 || carry > 0) {
        int digit1 = (i >= 0) ? num1[i] - '0' : 0;
        int digit2 = (j >= 0) ? num2[j] - '0' : 0;

        int sum = digit1 + digit2 + carry;
        result.push_back('0' + (sum % 10));
        carry = sum / 10;

        --i; --j;
    }

    // 結果目前是反序，需反轉
    reverse(result.begin(), result.end());
    return result;
}

int main() {
    string num1, num2;
    cout << "輸入第一個大整數: ";
    cin >> num1;
    cout << "輸入第二個大整數: ";
    cin >> num2;

    // 簡單輸入驗證
    auto isValid = [](const string& s) {
        return !s.empty() && all_of(s.begin(), s.end(), ::isdigit);
    };

    if (!isValid(num1) || !isValid(num2)) {
        cerr << "錯誤：輸入必須為非負整數" << endl;
        return 1;
    }

    string sum = addLargeNumbers(num1, num2);
    cout << "和 = " << sum << endl;

    // 測試案例
    cout << "\n--- 自動測試 ---" << endl;
    struct TestCase { string a, b, expected; };
    TestCase tests[] = {
        {"0", "0", "0"},
        {"1", "9", "10"},
        {"999", "1", "1000"},
        {"12345678901234567890", "98765432109876543210", "111111111011111111100"},
        {"99999999999999999999", "1", "100000000000000000000"}
    };

    for (const auto& t : tests) {
        string res = addLargeNumbers(t.a, t.b);
        cout << t.a << " + " << t.b << " = " << res 
             << (res == t.expected ? " ✓" : " ✗ 預期: " + t.expected) << endl;
    }

    return 0;
}

執行範例

輸入第一個大整數: 999999999999999999999999999999
輸入第二個大整數: 1
和 = 1000000000000000000000000000000

--- 自動測試 ---
0 + 0 = 0 ✓
1 + 9 = 10 ✓
999 + 1 = 1000 ✓
12345678901234567890 + 98765432109876543210 = 111111111011111111100 ✓
99999999999999999999 + 1 = 100000000000000000000 ✓

進階優化方向

• 基數擴大：改用基數 10⁹（每個 int32 存 9 位），減少迴圈次數，配合 64 位整數防溢位
• SIMD 向量化：利用 AVX2/AVX-512 並行處理多個數位
• FFT 乘法：超大整數乘法採用快速傅立葉變換 O(n log n)
• 記憶體池：避免頻繁分配/釋放，提升效能

擴展至其他運算