问题背景
实现 p o w ( x , n ) pow(x, n) pow(x,n)，即计算 x x x 的整数 n n n 次幂函数（即， x n x_n xn）。
数据约束
- − 100.0 < x < 100.0 -100.0 \lt x \lt 100.0 −100.0<x<100.0
- − 2 31 ≤ n ≤ 2 31 − 1 -2 ^ {31} \le n \le 2 ^ {31} -1 −231≤n≤231−1
- n n n 是一个整数
- 要么 x x x 不为零，要么 n > 0 n \gt 0 n>0。
- − 1 0 4 ≤ x n ≤ 104 -10 ^ 4 \le x_n \le 104 −104≤xn≤104
解题过程
快速幂，思想是任何一个幂都可以对半拆成两个规模减半的子问题，并用一次乘法来得到结果。
拆解过程中要计算的幂的指数，可以通过原问题的指数 n n n 的二进制表示来得到。
具体实现
class Solution {public double myPow(double x, int n) {double res = 1.0;// 处理指数为负的情况，转化为乘倒数if(n < 0) {n = -n;x = 1 / x;}while(n != 0) {// 如果 n 的当前数位上为 1，那么对应的幂需要作为子问题计算并累乘if((n & 1) == 1) {res *= x;}x *= x;n >>>= 1; // 处理完之后右移消除掉当前位}return res;}
}
