140. 快速幂

描述

计算 a^n % b，其中 a，b 和 n 都是 32 位的整数。

样例

例如 2^31 % 3 = 2
例如 100^1000 % 1000 = 0

挑战

O(logn)

思路

a ^ 2n = (a ^ n) * (a ^ n)
a ^ 2n + 1 = (a ^ n) * (a ^ n) * a
把幂次方拆成一半乘一半

代码

class Solution {
    /*
     * @param a, b, n: 32bit integers
     * @return: An integer
     */
    public int fastPower(int a, int b, int n) {
        if (n == 1) {
            return a % b;
        }
        if (n == 0) {
            return 1 % b;
        }
        
        // 用 long 类型不会有精度损失，结果准确
        long product = fastPower(a, b, n >> 1);
        product = (product * product) % b;
        if ((n & 0x1) == 1) {
            product = (product * a) % b;
        }
        return (int) product;
    }
}

注意

1. 位运算的左移替代除 2 和与运算替代取余更有效率
2. 答案是最终版本的优化算法，笨方法是用 for 循环从 1 循环到 n，比较没效率，但无论哪种做法都需要考虑底数为 0 并且幂次方为负的特殊情形。

下面是剑指offer书上的原话

代码

描述