BiruLyu
7/28/2017 - 11:43 PM

## 50. Pow(x, n)(#.java

``````/* This is a simple solution based on divide and conquer */

public class Solution {
public double pow(double x, int m) {
double temp=x;
if(m==0)
return 1;
temp=pow(x,m/2);
if(m%2==0)
return temp*temp;
else
{
if(m > 0)
return x*temp*temp;
else
return (temp*temp)/x;
}

}``````
``````/*

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

*/
//Solution1
class Solution {
public:
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;
}
};

//Solution2
class Solution {
public:
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;
}
};
``````
``````public class Solution {
public double myPow(double x, int n) {
if (n == 0) {
return 1;
}
if (n < 0) {
//n *= -1; 2.00000 ^ (-2147483648) output 0.00000
x = 1 / x;
}
return n % 2 == 0 ? myPow(x * x, Math.abs(n / 2)) : x * myPow(x * x, Math.abs(n / 2));
}
}``````