Java 實現大整數冪運算：以 5 的 20 次方為例，使用 BigInteger 避免溢位

題目要求

不使用 Math.pow 等系統函數，計算 5^20，並注意資料類型溢位臨界值。

解決方案：BigInteger 迭代相乘

import java.math.BigInteger;

public static BigInteger power(int base, int exponent) {
    BigInteger result = BigInteger.ONE;
    BigInteger b = BigInteger.valueOf(base);
    for (int i = 0; i < exponent; i++) {
        result = result.multiply(b);
    }
    return result;
}

// 呼叫
BigInteger ans = power(5, 20); // 95367431640625

進階優化：快速冪演算法 (Exponentiation by Squaring)

時間複雜度從 O(n) 降至 O(log n)：

public static BigInteger fastPower(int base, int exponent) {
    BigInteger result = BigInteger.ONE;
    BigInteger b = BigInteger.valueOf(base);
    int exp = exponent;
    while (exp > 0) {
        if ((exp & 1) == 1) result = result.multiply(b);
        b = b.multiply(b);
        exp >>= 1;
    }
    return result;
}

關鍵點

• int 最大值約 21 億，long 最大約 9×10^18，5^20 ≈ 9.5×10^13 超過 int 但未超 long，但題目要求通用大整數，故必須用 BigInteger。
• BigInteger 為不可變類，每次運算產生新物件，大指數時快速冪顯著提升效能。