题目要求
实现 pow(x, n) ，即计算 x 的整数 n 次幂函数（即x的n次方）。
破题思路
快速幂算法
求x的n次方最简单的方法是写一个n次的循环，每一次循环乘以一个x，那这样的话时间复杂度就是n。
快速幂法可以将时间复杂度下降到logn。
以下将从二进制和二分法两个角度进行解析
二进制角度
利用十进制数字 n 的二进制表示，可对快速幂进行数学化解释。
对于十进制整数n，可以化为二进制bm...b3b2b1；
则有二进制转十进制，（二进制转十进制的公式）
那么对于x的n次方，则有
，展开就是
所以根据以上推导，可以把求x的n次方转化成求上面那条公式的积。
所以，我们现在就要做的是两件事：
- 求出x²，x4，x的2m-1次方的值
- 求出b1,b2,b3的值。
所以在循环中，我们要求x的2的n次幂的话，就执行x = x²就行。
取bi的话，循环执行以下操作即可。
- n&1 （与操作）： 判断 n 二进制最右一位是否为 1 ；
- n>>1 （移位操作）： n 右移一位（可理解为删除最后一位）。
b的值只有两种情况，0和1，如果是1的话那就是x的2的某一个次方，0的话那就是1，用公式表示是这样的。
举个小例子。
分治法角度
快速幂实际上是分治思想的一种应用。
令 n/2 为整数，则需要分为奇偶两种情况（设向下取整除法符号为 "//" ）：
观察发现，当 n 为奇数时，二分后会多出一项 x 。
幂结果获取
- 根据推导，可通过循环 x=x2 操作，每次把幂从 n 降至 n//2 ，直至将幂降为 0 ；
- 设 res=1 ，则初始状态 xn=xn×res 。在循环二分时，每当 n 为奇数时，将多出的一项 x 乘入 res ，则最终可化至 xn=x0×res=res，返回 res 即可。
转化为位运算则是
- 取余数 n%2 等价于 判断二进制最右位 n&1 ；
- 向下整除 n//2 等价于 右移一位 n>>1 ；
算法流程
-
当 x=0.0 时：直接返回 0.0 ，以避免后续 1 除以 0 操作报错。分析： 数字 0 的正数次幂恒为 0 ； 0 的 0 次幂和负数次幂没有意义，因此直接返回 0.0 即可。
- 初始化 res=1 。
- 当 n<0 时：把问题转化至 n≥0 的范围内，即执行 x=1/x ，n=−n 。
- 循环计算：当 n=0 时跳出。
- 当 n&1=1 时：将当前 x 乘入 res （即 res∗=x ）。
- 执行 x=x2 （即 x∗=x ）。（给下一项）
- 执行 n 右移一位（即 n>>=1）。
5.返回res
class Solution {public double myPow(double x, int n) {if(x == 0.0f){return 0.0d;}long b = n;double res = 1.0d;//如果n<0,则按照幂小于0的方式来进行计算if(b < 0){x = 1 / x;b = -b;}while(b > 0){//首先处理n的低位if((b & 1) == 1){//如果低位为1，则进行计算//如果低位为0，那么结果是1，什么数的0次方都是1，可忽略res = res * x;}//下一项的x底数是上一项的平方x = x * x;//n右移一位b >>= 1;}return res;}
}手写流程
