# My answer using bit operation (C++ implementation)

• ``````class Solution {
public:
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;
}
};
``````

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).

• Interesting solution, but I think it uses too much extra space...

• how long is the running time?

• I used similar method, my C++ code costed 40ms.
Just one thing, in the second for statement, 32 should be 31, since the (1<<31) bit is sign bit.

• True and good suggestion. Though the 32 bit of n should always be zero as I turned n into a positive number.

• Its 4ms when I run it. Same as std::pow.

• is this o(1) time cost?

• cool solution, you can save more by putting them into one loop and stop when no further "1"s in n

``````double myPow(double x, int n) {
if(n<0){
x = 1.0/x;
n = -n;
}

double tbl[32] = {x};
unsigned int n_tmp = n;
double ret = (n_tmp & 1UL)?tbl[0]:1;

for(int i = 1; (1UL<< i) <= n_tmp; i++){
tbl[i] = tbl[i-1] * tbl[i-1];
ret *= (n_tmp & (1UL << i))?tbl[i]:1;
}
return ret;
}
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.