LeetCode50.Pow(x, n)

题目要求

实现 pow(x, n) ，即计算 x 的整数 n 次幂函数（即x的n次方）。

破题思路

快速幂算法

求x的n次方最简单的方法是写一个n次的循环，每一次循环乘以一个x，那这样的话时间复杂度就是n。

快速幂法可以将时间复杂度下降到logn。

以下将从二进制和二分法两个角度进行解析

二进制角度

利用十进制数字 n 的二进制表示，可对快速幂进行数学化解释。

 对于十进制整数n，可以化为二进制bm...b3b2b1；

则有二进制转十进制，（二进制转十进制的公式）

那么对于x的n次方，则有

，展开就是

所以根据以上推导，可以把求x的n次方转化成求上面那条公式的积。

所以，我们现在就要做的是两件事：

1. 求出x²，x4，x的2m-1次方的值
2. 求出b1,b2,b3的值。

所以在循环中，我们要求x的2的n次幂的话，就执行x = x²就行。

取bi的话，循环执行以下操作即可。

1. n&1 （与操作）： 判断 n 二进制最右一位是否为 1 ；
2. 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 ；

算法流程

1. 当 x=0.0 时：直接返回 0.0 ，以避免后续 1 除以 0 操作报错。分析： 数字 0 的正数次幂恒为 0 ； 0 的 0 次幂和负数次幂没有意义，因此直接返回 0.0 即可。

2. 初始化 res=1 。
3. 当 n<0 时：把问题转化至 n≥0 的范围内，即执行 x=1/x ，n=−n 。
4. 循环计算：当 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;
    }
}

 手写流程

原文地址：https://blog.csdn.net/Katharsis_2021/article/details/142878585

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！