首页 > 代码库 > LeetCode:Pow(x, n)

LeetCode:Pow(x, n)

要求

Implement pow(xn)

1. 特例

  • n=0, 直接返回1
  • n=1, 直接返回x
  • n<0,返回 1/pow(x,-n)

2. 优化

index = (n > 0 ? n : -n);
pow(x, index) = (index %2==1 ? pow(x, index/2)*x : pow(x, index/2));

 继续优化

pow(x, index) = (index %2==1 ? pow(x, index>>1)*x : pow(x, index>>1));

 

3. 参考代码

 class Solution 
 {
    public:
    double pow(double x, int n) 
    {
        int index = n;
        if (n == 0)
            return 1;
        if (n == 1)
            return x;
        if (n < 0)
            index = -n;
        double rev = index%2==0 ? pow(x*x, index>>1) : pow(x*x, index>>1)*x;
        if (n < 0)
            return 1 / rev;
        else
            return rev;
    }
 };