Above function can be optimized to O(logn) by calculating power(x, y/2) only once and storing it.
Let us extend the pow function to work for negative y and float x.
From http://www.programcreek.com/2012/12/leetcode-powx-n/
int power(int x, unsigned int y){ int temp; if( y == 0) return 1; temp = power(x, y/2); if (y%2 == 0) return temp*temp; else return x*temp*temp;}
public double myPow(double x, int n) {
if (n == 0) return 1;
if (x == 1) return 1;
if (x == -1) {
if (n % 2 == 0) return 1;
else return -1;
}
if (n == Integer.MIN_VALUE) return 0;
if (n < 0) {
n = -n;
x = 1/x;
}
double ret = 1.0;
while (n > 0) {
if ((n & 1) != 0)
ret *= x;
x = x * x;
n = n >> 1;
}
return ret;
}
思路1：利用整数n的二进制表达
性质：(x^y)^z = x^(y*z)
例如：(5^3)^2 = 5^3 * 5^3 = 5^(3*2)
10: 二进制(1010)b = (2^3)*1 + (2^2)*0 + (2^1)*1 + (2^0)*0
3^10 = 3^[(2^3)*1] * 3^[(2^2)*0] * 3^[(2^1)*1] * 3^[(2^0)*0]
res = 1
res = res^2 * 3^1 = 3^(1)b
res = res^2 * 3^0 = 3^2 = 3^(10)b
res = res^2 * 3^1 = 3^5 = 3^(101)b
res = res^2 * 3^0 = 3^10 = 3^(1010)b
需要特殊处理 n<0的情况。
性质：(x^y)^z = x^(y*z)
例如：(5^3)^2 = 5^3 * 5^3 = 5^(3*2)
10: 二进制(1010)b = (2^3)*1 + (2^2)*0 + (2^1)*1 + (2^0)*0
3^10 = 3^[(2^3)*1] * 3^[(2^2)*0] * 3^[(2^1)*1] * 3^[(2^0)*0]
res = 1
res = res^2 * 3^1 = 3^(1)b
res = res^2 * 3^0 = 3^2 = 3^(10)b
res = res^2 * 3^1 = 3^5 = 3^(101)b
res = res^2 * 3^0 = 3^10 = 3^(1010)b
需要特殊处理 n<0的情况。
double pow(double x, int n) { bool negPow = n<0 ? true : false; n = abs(n); double res = 1; for(int i=31; i>=0; i--) { res = res*res; if(n & (1<<i)) res = res*x; } if(negPow) res = 1/res; return res; }
double pow(double x, int n) { if(n>=0) return powPositive(x,n); else return 1/powPositive(x,-n); } double powPositive(double x, int n) { if(n==0) return 1; // base case double res = powPositive(x, n/2); res *= res; if(n%2) res *= x; return res; }
http://www.sigmainfy.com/blog/leetcode-powx-n.html
double bs(double x, int n) {
if (n == 0) return 1;
double ret = bs(x, n / 2);
if (n & 1)
return ret * ret * x;
else
return ret * ret;
}
double pow(double x, int n) {
if (abs(x) <= eps) return 0.0;
if (0 == n) return 1.0;
if (abs(abs(x) - 1.0) <= eps) {
if (n & 1) return x;
else
return 1.0;
}
double ret = x;
bool negative = n < 0;
n = abs(n);
ret = bs(x, n);
if (negative) return 1.0 / ret;
return ret;
}
- use |val – 0.0| < eps to test if the base x is equal to zero or not instead of using x == 0
1. nest myPow
double myPow(double x, int n) {
if(n<0) return 1/x * myPow(1/x, -(n+1));
if(n==0) return 1;
if(n==2) return x*x;
if(n%2==0) return myPow( myPow(x, n/2), 2);
else return x*myPow( myPow(x, n/2), 2);
}
2. double myPow
double myPow(double x, int n) {
if(n==0) return 1;
double t = myPow(x,n/2);
if(n%2) return n<0 ? 1/x*t*t : x*t*t;
else return t*t;
}
3. double x
double myPow(double x, int n) {
if(n==0) return 1;
if(n<0){
n = -n;
x = 1/x;
}
return n%2==0 ? myPow(x*x, n/2) : x*myPow(x*x, n/2);
}
4. iterative one
double myPow(double x, int n) {
if(n==0) return 1;
if(n<0) {
n = -n;
x = 1/x;
}
double ans = 1;
while(n>0){
if(n&1) ans *= x;
x *= x;
n >>= 1;
}
return ans;
}
5. bit operation
https://leetcode.com/discuss/12004/my-answer-using-bit-operation-c-implementation
In bit format and for a unsigned number, the number is represented as
k0*2^0 + k1*2^1 + ... +k31*2^31. Therefore, once we know the pow(x,2^0), pow(x,2^1), ..., pow(x,2^31), we can get pow(x,n). And pow(x,2^m) can be constructed easily as pow(x,2^m) = pow(x,2^(m-1)*pow(x,2^(m-1).
double pow(double x, int n) {
if(n<0){
x = 1.0/x;
n = -n;
}
int unsigned m = n;
double tbl[32] = {0};
double result = 1;
tbl[0] = x;
for(int i=1;i<32;i++){
tbl[i] = tbl[i-1]*tbl[i-1];
}
for(int i=0;i<32;i++){
if( m & (0x1<<i) )
result *= tbl[i];
}
return result;
}
https://leetcode.com/discuss/17005/short-and-easy-to-understand-solution
https://leetcode.com/discuss/17005/short-and-easy-to-understand-solution
public double pow(double x, int n) {
if(n == 0)
return 1;
if(n<0){
n = -n;
x = 1/x;
}
return (n%2 == 0) ? pow(x*x, n/2) : x*pow(x*x, n/2);
}
should we add if(x == 0) return 0;
the type of x is double you can't use if(x==0)
//O(lgn) public static int powRec(int x, int y){ if(y == 0){ return 1; } if(y == 1){ return x; } int pow = powRec(x, y/2); if((y&1) != 0){ return pow*pow*x; } else{ return pow*pow; } } //O(lgn) public static int powIter(int x, int y){ int pow = 1; if(y == 0){ return 1; } if(y == 1){ return x; } while(y > 0){ //if y is odd if((y&1) != 0){ pow*=x; } //divide by 2 y >>= 1; //calclate x^2 x = x*x; } return pow; }
Let us extend the pow function to work for negative y and float x.
From http://www.programcreek.com/2012/12/leetcode-powx-n/
public double power(double x, int n) { if (n == 0) return 1; double v = power(x, n / 2); if (n % 2 == 0) { return v * v; } else { return v * v * x; } } public double pow(double x, int n) { if (n < 0) { return 1 / power(x, -n); } else { return power(x, n); } }
float power(float x, int y){ float temp; if( y == 0) return 1; temp = power(x, y/2); if (y%2 == 0) return temp*temp; else { if(y > 0) return x*temp*temp; else return (temp*temp)/x; }}public double pow(double x, int n) {
if(n==0)
return 1.0;
double res = 1.0;
if(n<0)
{
if(x>=1.0/Double.MAX_VALUE||x<=1.0/-Double.MAX_VALUE)
x = 1.0/x;
else
return Double.MAX_VALUE;
if(n==Integer.MIN_VALUE)
{
res *= x;
n++;
}
}
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;
}
以上代码中处理了很多边界情况，这也是数值计算题目比较麻烦的地方。比如一开始为了能够求倒数，我们得判断倒数是否越界，后面在求指数的过程中我们也得检查有没有越界。所以一般来说求的时候都先转换为正数，这样可以避免需要双向判断（就是根据符号做两种判断）。接下来我们介绍二分法的解法，如同我们在Sqrt(x)的方法。不过这道题用递归来解比较容易理解，把x的n次方划分成两个x的n/2次方相乘，然后递归求解子问题，结束条件是n为0返回1。因为是对n进行二分，算法复杂度和上面方法一样，也是O(logn)。代码如下：
Read full article from Write a C program to calculate pow(x,n) | GeeksforGeeks
