No.50 Pow(x,n)

Implement pow(x, n).

Tags Math Binary Search

编写函数pow(x,n)

之前想的太过简单，只是分情况讨论，然后输出结果，但没有注意到效率，并且一些违法输入不知道如何表示。

注意事项：

对于整数处理，比较重要的注意点在于符号和处理越界的问题
一般来说，数值计算的题目可以用两种方法来解，一种是以2为基进行位处理的方法，另一种是用二分法。

　　　位处理：

　　　使用位运算进行数值计算的优化：

　　　　　任何一个整数可以表示成以2的幂为底的一组基的线性组合，即num=a_0*2^0+a_1*2^1+a_2*2^2+...+a_n*2^n。

　　　　基于以上这个公式以及左移一位相当于乘以2，可以先让除数左移直到大于被除数之前得到一个最大的基。然后接下来我们每次尝试减去这个基，

　　　　如果可以则结果增加加2^k,然后基继续右移迭代，直到基为0为止。因为这个方法的迭代次数是按2的幂直到超过结果，所以时间复杂度为O(logn)。

　　　　对于本题，相当于x^n = x^(a_0*2^0+a_1*2^1+a_2*2^2+...+a_n*2^n)=(x^(a_0*2^0))*(x^(a_1*2^1))*...*(x^(a_n*2^n))

1 while(n)
2 {
3     if(n & 1)
4         value *= x;
5     x *= x;
6     n >>= 1;
7 }

第一次提交：超时

 1 #include "stdafx.h"
 2 #include <iostream>
 3 using namespace std;
 4 
 5 class Solution
 6 {
 7 private:
 8     bool isValid;//标识结果是否有效
 9 public:
10     double myPow(double x, int n)
11     {
12         /*    
13              实现函数pow(x,n):
14            将n分为3类：正、负、0
15            将x分为   ：0、非0
16            疑问：0^0 = 不存在？
17                  不存在返回什么？
18                  浮点数判零
19         */
20         isValid = true;
21         if(n > 0 && x == 0.0)
22             return 0.0;
23         if((n < 0 && x == 0.0) || (n==0 && x == 0.0))
24         {
25             isValid = false;
26             return 0.0;
27         }
28         if(n==0 && x != 0.0)
29             return 1.0;
30         double value = 1.0;
31         bool isNegative = false;
32         if(n < 0)//之前没注意！！！
33         {
34             n = -n;
35             isNegative = true;
36         }
37         while(n)
38         {
39             value *= x;
40             n--;
41         }
42         return isNegative ? 1/value : value;
43     }
44 };
45 
46 int main()
47 {
48     Solution sol;
49     cout << sol.myPow(-2,0)<<endl;
50     return 0;

51 }

View Code

第二次提交：超时【参考之后】

 1 class Solution
 2 {
 3 private:
 4     bool isValid;//标识结果是否有效
 5 public:
 6     double myPow(double x, int n)
 7     {
 8         /*    
 9              实现函数pow(x,n):
10            将n分为3类：正、负、0
11            将x分为   ：0、非0
12            疑问：0^0 = 不存在？
13                  不存在返回什么？
14                  浮点数判零
15         */
16         isValid = true;
17         if(n > 0 && x == 0.0)
18             return 0.0;
19         if((n < 0 && x == 0.0) || (n==0 && x == 0.0))
20         {
21             isValid = false;
22             return 0.0;
23         }
24         if(n==0 && x != 0.0)
25             return 1.0;
26         double value = 1.0;
27         bool isNegative = false;
28         if(n < 0)//之前没注意！！！
29         {
30             n = -n;
31             isNegative = true;
32         }
33         while(n)
34         {
35             if(n & 1)
36                 value *= x;
37             x *= x;
38             n >>= 1;
39             
40         }
41         return isNegative ? 1/value : value;
42     }
43 };

View Code

Last executed input: 1.00000, -2147483648

第三、第四、第五次提交【都是因为考虑不周，与1和-1有关】

最终版本：注意1与-1的特殊性，且对于-1，不要想当然，举例来做

 1 #include "stdafx.h"
 2 #include <iostream>
 3 using namespace std;
 4 
 5 class Solution
 6 {
 7 private:
 8     bool isValid;//标识结果是否有效
 9 public:
10     double myPow(double x, int n)
11     {
12         /*    
13              实现函数pow(x,n):
14            将n分为3类：正、负、0
15            将x分为   ：0、1、-1、非0、1、-1
16            疑问：0^0 = 不存在？
17                  不存在返回什么？
18                  浮点数判零
19         */
20         isValid = true;
21         if(n > 0 && x == 0.0)
22             return 0.0;
23         if((n < 0 && x == 0.0) || (n==0 && x == 0.0))
24         {
25             isValid = false;
26             return 0.0;
27         }
28         if(n==0 && x != 0.0)
29             return 1.0;
30         if(x == 1.0)//!!!
31             return 1.0;
32         if(x == -1)//!!!
33             return (n&1) ? -1.0 : 1.0; //!!!
34         double value = 1.0;
35         bool isNegative = false;
36         if(n < 0)//之前没注意！！！
37         {
38             n = -n;
39             isNegative = true;
40         }
41         while(n)
42         {
43             if(n & 1)
44                 value *= x;
45             x *= x;
46             n >>= 1;
47             
48         }
49         return isNegative ? 1/value : value;
50     }
51 };
52 
53 int main()
54 {
55     Solution sol;
56     cout << sol.myPow(0.00001,2147483647)<<endl;
57     return 0;
58 }

参考：Pow(x, n) -- LeetCode

　　　Divide Two Integers -- LeetCode