if n is negative, first take a multiplication, and then make n-- , lastly n=-n

public class Solution {
public double myPow(double x, int n) {
if (n==0)return 1.0;
double t = 1.0;
if (n<0){
x = 1.0/x;
n = -(n+1);
t *= x;
}
while (n>=1){
if ((n&1)==1)
t *= x;
x *= x;
n = n>>1;
}
return t;
}
}

Thanks for such a nice solution！ The extra variable m can be removed:

class Solution {
public:
double myPow(double x, int n) {
double p = 1;
for (x = n > 0 ? x : 1 / x; n; n /= 2, x *= x) {
if (n & 1) {
p *= x;
}
}
return p;
}
};

He's basically using bitwise operators to check for an odd number (m & 1) and to floor-divide by 2 (m >>= 1).

This is the equivalent of the following (without bitwise operators):

def myPow(self, x, n):
m = abs(n)
ans = 1.0
while m:
if m % 2:
ans *= x
x *= x
m //= 2
return ans if n >= 0 else 1 / ans

Shifting all the bits 1 to the right (m >>= 1) has the effect of cutting an integer in half and dropping the remainder. The bitwise and (m & 1) basically compares the last bit in m with the single bit in 1, and if they're both 1 then it evaluates to 1 (otherwise it evaluates to 0). So odd m will evaluate to 1 (or True), and even m will evaluate to 0 (or False).

@jaewoo If the n=-2147483648, would it not be your result =1? I just do not see how your code avoids the error symao's code makes. I mean your code will not get into infinite loop, but it does not give right answer for cases like pow(2, -2147483648) for eg.

I'm in support that it's not O(1), O(log n) instead. Your runtime still grow when n grows. Or u sing your way of proof, all algorithm with only Integer input is O(1), since they bounded in O(2^32).