首页 > 代码库 > leetcode第一刷_Pow(x, n)

leetcode第一刷_Pow(x, n)

快速乘方的算法,写了好多变,出了各种错,真是服了我自己了。

思想是每次对n减半,将当前的temp平方。需要注意的是如果当前的n是个奇数,减半之后会丢失掉一次乘积,因此如果当前的n为奇数,应该先在结果里面乘一个temp。

还有,n可能是负数,负数的次方最后要求一次倒数。

class Solution {
public:
    double pow(double x, int n) {
        if(n == 0)
            return 1;
        if(n == 1)
            return x;
        double res = 1, temp = x;
        bool neg = false;
        if(n<0){
            neg = true;
            n = -n;
        }
        while(n>0){
        	if(n&1)
        		res *= temp;
            temp *= temp;
            n /= 2;
        }
        if(neg)
            return (double)1.0/res;
        return res;
    }
};