快速冪算法詳解：O(log n) 計算 a^n 的高效實現

前言

計算 a^n（n 為非負整數）是經典算法問題。暴力循環乘法時間複雜度 O(n)，當 n 極大（如 10^9）時不可接受。本文詳解「快速冪」（Exponentiation by Squaring）算法，將複雜度降至 O(log n)，並給出遞歸與迭代兩種 Java 實現，解析位運算優化細節。

核心數學原理

利用冪的性質分解指數：

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

每步將指數減半，遞歸深度/循環次數為 log₂(n)。

遞歸實現（教科書式）

public class FastPower {
    public static double power(double base, int exponent) {
        if (exponent == 0) return 1;
        if (exponent == 1) return base;

        double half = power(base, exponent >> 1); // exponent / 2
        double result = half * half;              // 平方
        if ((exponent & 1) == 1) {                // 奇數檢查
            result *= base;
        }
        return result;
    }

    public static void main(String[] args) {
        System.out.println(power(5.5, 5)); // 5032.84375
    }
}

關鍵位運算優化解析

現代 JVM JIT 編譯器會自動優化 /2 和 %2，但位運算寫法更明確表達意圖，且在嵌入式/底層場景有優勢。

迭代實現（生產環境推薦）

避免遞歸棧溢出，常數空間 O(1)：

public static double powerIter(double base, int exponent) {
    if (exponent < 0) { // 支持負指數
        base = 1 / base;
        exponent = -exponent;
    }
    double result = 1;
    while (exponent > 0) {
        if ((exponent & 1) == 1) {
            result *= base;
        }
        base *= base;
        exponent >>= 1;
    }
    return result;
}

邏輯：從二進制最低位開始，若該位為 1，累乘當前 base；每輪 base 自乘（平方），指數右移。

擴展：模冪運算 (a^n mod m)

竞賽編程/加密常需求，防溢出：

public static long modPow(long a, long n, long mod) {
    long res = 1 % mod;
    a %= mod;
    while (n > 0) {
        if ((n & 1) == 1) res = (res * a) % mod;
        a = (a * a) % mod;
        n >>= 1;
    }
    return res;
}

複雜度分析

• 時間：O(log n) — 循環/遞歸次數 = 二進制位數
• 空間：遞歸 O(log n) 棧深度；迭代 O(1)

常見陷阱與注意點

1. 指數為 0：直接返回 1（含 0^0 按約定返回 1）
2. 負指數：轉為正指數計算倒數，注意 Integer.MIN_VALUE 取反溢出，建議用 long 接收
3. 浮點數精度：大指數下誤差累積，金融/科學計算考慮 BigDecimal 或對數運算
4. 溢出：整數冪結果極大，需配合取模或用 BigInteger

總結

快速冪是「分治 + 位運算」的經典範例，將 O(n) 降為 O(log n)。掌握遞歸與迭代兩種寫法，理解 >>=1、&1 的本質，能在算法面試、競賽編程、密碼學實現中遊刃有餘。生產代碼推薦迭代版，並根據業務添加邊界檢查與取模邏輯。