Loading... # 快速幂 注意到 $$ X^{62} = (X^{31})^2 \\ X^{31} = (X^{15})^2 \times X\\ X^{15} = (X^7)^2 \times X\\ X^7 = (X^3)^2 \times X\\ X^3 = X^2 \times X $$ 至多进行两次乘法操作,可以将问题的规模缩小为原来的一半。所以,需要进行的乘法次数不超过2logN。 ## 一个简单的递归实现 ```java public static long pow1(long base, int exponent) { // 基准情况 if (exponent == 0) return 1; if (exponent == 1) return base; if (exponent % 2 == 0) { return pow1(base * base, exponent / 2); } else { return pow1(base * base, exponent / 2) * base; } } ``` ## 优化后的递归实现 上面代码中第四行的判断其实是不必要的,因为 N = 1 的情形也可以正常处理。如果我们删除无用的判断,并尽可能地使用位运算可以得到下面代码。 ```java public static long pow2(long base, int exponent) { // 基准情况 if (exponent == 0) return 1; if ((exponent & 1) == 0) { return pow2(base * base, exponent >> 1); } else { return pow2(base * base, exponent >> 1) * base; } } ``` ## 使用循环代替递归 进一步优化,我们使用循环代替递归。 ```java public static long pow3(long base, int expoent) { if (expoent == 0) return 1; long result = 1; while(expoent != 1) { if ((expoent & 1) == 1) { result *= base; } expoent >>= 1; base *= base; } result *= base; return result; } ``` 最后修改:2020 年 04 月 11 日 © 允许规范转载 赞 0 如果觉得我的文章对你有用,请随意赞赏