C 語言大整數實現：數組存儲與字符串互轉核心算法詳解

為什麼需要大整數

C 語言基本類型（long long 64 位）最大約 9.22e18（19 位），超出範圍的整數（如 100 位、1000 位）無法直接存儲，需自定義結構。

數組存儲設計

• 基數選擇：每個元素存 4 位（基數 10000）或 9 位（基數 1e9，配合 64 位中間變量），平衡空間與乘法溢出風險；
• 順序約定：a[0] 存**最低位**（個位段），a[len-1] 存最高位，便於進位傳遞；
• 結構體封裝：

typedef struct {
    int digits[ MAX_LEN ]; // 每元素存 4 位十進制
    int len;               // 有效位段數
    int sign;              // 1 正，-1 負
} BigInt;

字符串 → 大整數

void fromString(BigInt *b, const char *s) {
    memset(b, 0, sizeof(BigInt));
    if (*s == '-') { b->sign = -1; s++; }
    int n = strlen(s);
    for (int i = n - 1; i >= 0; i -= 4) {
        int l = max(0, i - 3);
        int segment = 0;
        for (int j = l; j <= i; j++) segment = segment * 10 + (s[j] - '0');
        b->digits[b->len++] = segment;
    }
    trim(b); // 去除高位前導零段
}

大整數 → 字符串

void toString(const BigInt *b, char *buf) {
    if (b->len == 0) { strcpy(buf, "0"); return; }
    char *p = buf;
    if (b->sign == -1) *p++ = '-';
    sprintf(p, "%d", b->digits[b->len - 1]); // 最高位不補零
    p += strlen(p);
    for (int i = b->len - 2; i >= 0; i--) {
        sprintf(p, "%04d", b->digits[i]); // 低位補零到 4 位
        p += 4;
    }
    *p = '\0';
}

進階運算提示

• 加減法：逐段運算 + 進位/借位，O(n)；
• 乘法：模擬豎式乘法 O(n²)，大數字可升級 Karatsuba / FFT；
• 比較：先比 len，再從高位段向低位段逐段比較。

現成庫推薦

生產環境請直接使用成熟庫：

• GMP (C/C++)：工業級、極致性能；
• OpenSSL BIGNUM：密碼學場景首選；
• C++ Boost.Multiprecision / C# BigInteger / Java BigInteger：高級語言內置。