首页 > 代码库 > pox(x,n)
pox(x,n)
Implement pow(x, n).
如何实现pow(x,n),最原始的方法是用一层循环，求n个x的乘积，代码如下：
1 class Solution { 2 public: 3 double pow(double x, int n) { 4 if(n<0) 5 return 1.0/pow(x,-n); 6 int i; 7 for(i=0;i<n;i++) 8 { 9 x*=x;10 }11 return x;12 }13 };
但是这样做时间复杂度太高了，超时，不行啊!
联想到二分法，这一题也能够用二分的思路。因为x^n=(x^(n/2))^2.很简单，直接上ac的代码了！
1 class Solution { 2 public: 3 double pow(double x, int n) { 4 if(n==0) 5 return 1.0; 6 if(n<0) 7 { 8 if(n==INT_MIN) 9 return 1.0 / (pow(x,INT_MAX)*x); 10 else 11 return 1.0 / pow(x,-n); 12 } 13 double half=pow(x,n>>1);14 if(n%2==0)15 return half*half;16 else17 return half*half*x;//如果n为奇数的话，要多乘一个x来弥补。18 19 }20 };
有没有更好的思路呢？参考了一下他人的代码，收获很大！原来可以这么弄！请不要忘记，计算机中存储数字的方式是直接存储其二进制数。例如:5=1001,当n=5时，pow(x.n)=x^1001=x^1000*x^1，那么，我们可以从n二进制位最后一位开始，每次右移一位，如果二进制位为1，就将结果乘以x，每右移一位，就执行x*=x(相当于把指数左移了一位)，直至n为0为止，这样就可以了。以下是ac的代码：
1 class Solution { 2 public: 3 double pow(double x, int n) { 4 if(n==0) 5 return 1.0; 6 if(n<0){ 7 if(n==INT_MIN) 8 return 1.0 / (pow(x,INT_MAX)*x); 9 else 10 return 1.0 / pow(x,-n); 11 }12 13 double end=1.0;14 for(;n>0;x*=x,n>>=1){15 if(n&1>0)16 end*=x;17 }18 return end;19 }20 };
我们注意到，所有ac的代码都对INT_MIN做了特殊处理，因为，计算机中储存数据是以补码的形式，而补码表示负数比表示正数能多表示一位！所以|INT_MIN|=|INT_MAX+1|,那就是说-INT_MIN=INT_MAX+1!所以要多乘上一个x！
pox(x,n)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。