leetcode Pow(doubule x,int n)

今天第一天开通博客，心情还是小激动的

上代码：

方法一：常规递归，x的n次方={x^n/2*x^n/2//n为偶

x^n/2*x^n/2 *x //n为奇数

}

 1 class Solution {
 2 public:
 3     bool isinvalid=false;                 //全局标记，标记是否是非法
 4     double pow(double x, int n) {
 5         if(((x-0.0)>-0.0000001&&(x-0.0)<0.0000001)&&n<0)   //注意，这里是比较x是否为零，网上多数没有该功能，o的负数次方，显然不行
 6         {
 7             isinvalid=true;
 8             return 0.0;
 9         }
10         
11         if(n==0)  return 1.0;                             //0 次方为1
12                                     
13         if(n<0)
14         {
15             return 1.0/recuryPow(x,-n);                //为什么这里的INT_MIN就没问题呢，这里没问题，是因为-n后其实还是个负数，传过去个负数
16         }
17         else
18         {
19             return recuryPow(x,n);
20         }
21     }
22     double recuryPow(double x,int n)                   //这时当上面传过来是INT_MIN加负号传过来的时候，n还是INT_MIN，因为ＩＮＴ＿ＭＡＸ装不下，n还是负数为INT_MIN                   
23     {
24         if(n==0)
25         {
26             return 1.0;
27         }
28         if(n==1)                              //如果n为负，就不会走n==1，只可能n=-1，但是如果n=-1，后面recuryPow(x,-1)就等于1.0，然后因为-1为奇数，所以也相当于反回了x
29         {
30             return x;
31         }
32         double a=recuryPow(x,n/2);
33         if(n&1)                                      //为奇数，无所谓正负，也可以n%2求余，负数也可以用该方法判断奇数偶数
34         {
35             return a*a*x;
36         }
37         else
38         {
39             return a*a;
40         }
41     }
42 };

方法二：除了上述方法，这里还提到了一种十分巧妙并且快速的方法，原文描述如下（效率快来很多）：

Consider the binary representation of n. For example, if it is "10001011", then x^n = x^(1+2+8+128) = x^1 * x^2 * x^8 * x^128. Thus, we don't want to loop n times to calculate x^n. To speed up, we loop through each bit, if the i-th bit is 1, then we add x^(1 << i) to the result. Since (1 << i) is a power of 2, x^(1<<(i+1)) = square(x^(1<<i)). The loop executes for a maximum of log(n) times.

该方法通过扫描n的二进制表示形式里不同位置上的1，来计算x的幂次

确实很巧妙

为了正确计算x的n次幂，还需要考虑到以下一些情况：

1) x取值为0时，0的正数次幂是1，而负数次幂是没有意义的；判断x是否等于0不能直接用“==”。

2) 对于n取值INT_MIN时，-n并不是INT_MAX，这时需要格外小心。（前面用的）

3) 尽量使用移位运算来代替除法运算，加快算法执行的速度。

代码实现：

 1 double my_pow(double x, int n)  
 2 {  
 3     if(n==0)  
 4             return 1.0;  
 5     if(n<0)  
 6         return 1.0 / pow(x,-n);  
 7     double ans = 1.0 ;  
 8     for(; n>0; x *= x, n>>=1)  
 9     {  
10         if(n&1>0)  
11             ans *= x;  
12     }  
13     return ans;  
14 }

我的代码实现

 1 class Solution {
 2 public:
 3     bool isinvalid=false;
 4     double pow(double x, int n) {
 5         if(((x-0.0)>-0.0000001&&(x-0.0)<0.0000001)&&n<0)   //x==0 case
 6         {
 7             isinvalid=true;
 8             return 0.0;
 9         }
10         
11         if(n==0)  return 1.0;                             //0 ci fang dengyu 1
12         double result=1.0;                                    //fang hui de ke neng chaoguo double 
13         
14         if(n<0) 
15         {
16             if(n==INT_MIN)                             //这里很有意思，因为最小负数变成正数比最大正整数还大一，所以要单独处理
17             {
18                 return 1.0/(myPow(x,INT_MAX)*x);              
19             }
20             else
21             return 1.0/myPow(x,-n);
22         }
23         else
24         {
25             return myPow(x,n);
26         }
27     }
28     double myPow(double x,int n)                   //变成只处理n大于0的情况，如果上面传过来个负数，while那就成死循环了
29     {
30        double result=1.0;
31        while(n)
32        {
33            if(n&1)                                //这里是看每一位是否为1，而不是看是奇偶
34            {
35                result*=x;
36            }
37            n=n>>1;                            //就算改为n/2表示右移，这里n就可以为负，但上面不行
38            x=x*x;                             //100010  x,x^2,x²*x²=x⁴,x⁸,x¹⁶,x³²    
39        }
40        return result;
41        
42     }
43 };