再谈快速幂的非递归算法

我们只要看n的二进制表示，如果是1，就把对应的乘上去。如果不是，那么因子继续跟新。这就是快速幂非递归算法的关键的地方。

理解快速幂的思路是最重要的，就算要记忆结论，也不是去记忆代码怎么写，而是去记忆x的幂次和答案的关系，每一位都要对x做累乘，但只有二进值为1的时候，才乘到代码里面。

typedef long long LL;
class Solution {
public:
    double myPow(double x, int n) {
        LL N = n;
        return (N>=0?_myPow(x,N):_myPow(1/x,-N));
    }

    double _myPow(double x, long long n){
        double res = 1;
        while(n){
            if(n&1) res*=x;
            x*=x;
            n>>=1;
        }
        return res;
    }
};

版权声明：本文来源CSDN，感谢博主原创文章，遵循 CC 4.0 by-sa 版权协议，转载请附上原文出处链接和本声明。
原文链接：https://blog.csdn.net/wwxy1995/article/details/106892760
站方申明：本站部分内容来自社区用户分享，若涉及侵权，请联系站方删除。

发表于 2020-06-28 01:28:07
阅读 ( 1402 )
分类：算法

再谈快速幂的非递归算法

你可能感兴趣的文章

精选的优质文章

0 条评论

官方社群

GO教程

推荐文章

猜你喜欢

随便看看