题目描述:
实现 pow(x, n) ,即计算 x 的 n 次幂函数。
样例:
输入: 2.00000, 10
输出: 1024.00000
说明:
-100.0 < x < 100.0
n 是 32 位有符号整数,其数值范围是 [-2147483648, 2147483647] 。
分析:
计算x 的 n 次幂:如果采用常规解法循环n次对想相乘,当x=0.000001,n=2147483647会超时。
所以考虑x的n次幂等于x的n/2次幂x的n/2次幂(n为偶数时)
n为奇数时x的n次幂等于x的(n-1)/2次幂x的(n-1)/2次幂
要注意考虑到x=0和n=-2147483648的情况。
public double myPow(double x, int n) {
if(x==0)
return 0;
if(x==1)
return 1;
if(n==0)
return 1;
double re=1;
double temp=x;
int i=0;
if(n<0&&n!=Integer.MIN_VALUE)
i=-n;
else if(n==Integer.MIN_VALUE)
i=Integer.MAX_VALUE;
else
i=n;
for(;i!=0;i=(i>>1)) {
if((i&1)==1)
re=re*x;
x=x*x;
}
if(n<0) {
if(n==Integer.MIN_VALUE)
re*=temp;
re=1.0/re;
}
return re;
}