Not Only Algorithm,不仅仅是算法,关注数学、算法、数据结构、程序员笔试面试以及一切涉及计算机编程之美的内容 。。
你的位置:NoAlGo博客 » 题解 » 

Leetcode Pow(x, n)

Leetcode algorithms 第 50 题:Pow(x, n)。

题目

Implement pow(xn).

解答

求x的n次方,直接使用二分快速幂算法,对指数进行二分。这里需要注意n为负数的情形。

具体代码如下:

class Solution {
public:
    double pow(double x, int n) { //快速幂取模
        bool neg = 0;
        unsigned int exp = n; //unsigned, -2147483648取反后int溢出
        if (n < 0) exp = -n, neg = 1;
        
        double ans = 1, q = x;
        while (exp)
        {
            if (exp & 1) ans *= q;
            exp >>= 1, q = q * q;
        }
        
        return neg ? 1.0/ans : ans;
    }
};
上一篇: 下一篇:

我的博客

NoAlGo头像编程这件小事牵扯到太多的知识,很容易知其然而不知其所以然,但真正了不起的程序员对自己程序的每一个字节都了如指掌,要立足基础理论,努力提升自我的专业修养。

站内搜索

最新评论