第一种方法在Divide Two Integers使用过，就是把n看成是以2为基的位构成的，因此每一位是对应x的一个幂数，然后迭代直到n到最高位。比如说第一位对应x，第二位对应x*x,第三位对应x^4,...,第k位对应x^(2^(k-1)),可以看出后面一位对应的数等于前面一位对应数的平方，所以可以进行迭代。因为迭代次数等于n的位数，所以算法的时间复杂度是O(logn)。代码如下：
public double pow(double x, int n) {
if(n==0)
return 1.0;
if(n<0)
{
if(x>=0 && x>=1.0/Double.MAX_VALUE||x<0&&x<=1.0/Double.MIN_VALUE)
x = 1.0/x;
else
return Double.MAX_VALUE;
}
double res = 1.0;
n = Math.abs(n);
boolean isNeg = false;
if(n%2==1 && x<0)
{
isNeg = true;
}
x = Math.abs(x);
while(n>0)
{
if((n&1) == 1)
{
if(res>Double.MAX_VALUE/x)
return Double.MAX_VALUE;
res *= x;
}
x *= x;
n = n>>1;
}
return isNeg?-res:res;
}以上代码中处理了很多边界情况，这也是数值计算题目比较麻烦的地方。比如一开始为了能够求倒数，我们得判断倒数是否越界，后面在求指数的过程中我们也得检查有没有越界。所以一般来说求的时候都先转换为正数，这样可以避免需要双向判断（就是根据符号做两种判断）。double pow(double x, int n) {
if (n == 0) return 1.0;
double half = pow(x, n/2);
if (n%2 == 0)
{
return half*half;
}
else if (n>0)
{
return half*half*x;
}
else
{
return half/x*half;
}
}以上代码比较简洁，不过这里有个问题是没有做越界的判断，因为这里没有统一符号，所以越界判断分的情况比较多，不过具体也就是在做乘除法之前判断这些值会不会越界，有兴趣的朋友可以自己填充上哈，这里就不写太啰嗦的代码了。不过实际应用中健壮性还是比较重要的，而且递归毕竟会占用递归栈的空间，所以我可能更推荐第一种解法。Pow(x, n) -- LeetCode,布布扣,bubuko.com
原文：http://blog.csdn.net/linhuanmars/article/details/20092829