快速冪演算法：遞歸分治 + 位運算優化，O(log n) 計算 a^n

計算 a^n (n 為非負整數) 是經典演算法題。暴力循環 O(n) 在大指數下極慢，快速冪 (Exponentiation by Squaring) 利用 a^n = (a^(n/2))^2 特性，配合位運算將複雜度降為 O(log n)。本文從數學推導到 Java 實現完整解析。

數學推導

n 為偶數：a^n = a^(n/2) * a^(n/2)
n 為奇數：a^n = a^((n-1)/2) * a^((n-1)/2) * a

遞歸基準：n=0 → 1、n=1 → a

位運算優化對應

Java 完整實現 (遞歸版)

public class FastPower {

    /**
     * 計算 base^exponent (exponent >= 0)
     * 時間複雜度 O(log n)，空間複雜度 O(log n) 遞歸棧
     */
    public static double power(double base, int exponent) {
        if (exponent == 0) return 1;
        if (exponent == 1) return base;

        // 遞歸計算 base^(exponent/2)
        double half = power(base, exponent >> 1); // exponent / 2
        double result = half * half;                // 平方

        // 若指數為奇數，再乘一次 base
        if ((exponent & 1) == 1) { // exponent % 2 == 1
            result *= base;
        }
        return result;
    }

    // 測試
    public static void main(String[] args) {
        System.out.println(power(5.5, 5));  // 5032.84375
        System.out.println(power(2, 10));   // 1024.0
        System.out.println(power(3, 0));    // 1.0
    }
}

迭代版 (空間 O(1)，生產環境首選)

public static double powerIterative(double base, int exponent) {
    double result = 1;
    double current = base;
    int exp = exponent;

    while (exp > 0) {
        if ((exp & 1) == 1) {      // 當前位為 1
            result *= current;      // 累乘
        }
        current *= current;         // 平方：base^(2^i)
        exp >>= 1;                 // 右移處理下一位
    }
    return result;
}

迭代邏輯：將指數拆解為二進位，exp=13 (1101b) → base^1 * base^4 * base^8。

擴展：支援負指數與模冪

// 負指數
public static double power(double base, int exponent) {
    if (exponent < 0) return 1 / power(base, -exponent);
    // ... 原邏輯
}

// 模冪 (a^b % mod) - 密碼學核心
public static long modPow(long base, long exponent, long mod) {
    long result = 1 % mod;
    base %= mod;
    while (exponent > 0) {
        if ((exponent & 1) == 1) result = (result * base) % mod;
        base = (base * base) % mod;
        exponent >>= 1;
    }
    return result;
}

效能對比 (n = 1,000,000,000)

總結

• 核心公式：a^n = (a^(n/2))^2 * (n%2==1 ? a : 1)
• 位運算替換：/2 → >>1、%2 → &1，CPU 指令級優化
• 生產環境用迭代版：避免遞歸棧溢出、空間 O(1)
• 擴展性強：矩陣快速冪、模冪、橢圓曲線加密皆基於此思想