Calculate x to the power of n

Problem Description
Implement pow(x, n) where x is a float and n is an integer.

Solutions
Analysis: This problem is pretty simple. We can calculate it in O(n) time. But we can also easily do it in O(log n ) time.

I. Recursive Solution - O(log n)

view plainprint?

1. class Solution:  
2.     # @param {float} x  
3.     # @param {integer} n  
4.     # @return {float}  
5.     def myPow(self, x, n):  
6.         if n == 0: return 1  
7.         result = self.myPow(x, n/2) if n>0 else self.myPow(1/x, -(n/2))  
8.         return result * result * (x if n % 2 == 1 else 1)  

class Solution:
    # @param {float} x
    # @param {integer} n
    # @return {float}
    def myPow(self, x, n):
        if n == 0: return 1
        result = self.myPow(x, n/2) if n>0 else self.myPow(1/x, -(n/2))
        return result * result * (x if n % 2 == 1 else 1)

II. Non-recursive Solution - O(log n) time - O(log n) space
This solution use one additional array, which is quite obvious.

view plainprint?

1. class Solution:  
2.     # @param {float} x  
3.     # @param {integer} n  
4.     # @return {float}  
5.     def myPow(self, x, n):  
6.         if n == 0: return 1  
7.         result = 1  
8.         a = []  
9.         t = n if n>0 else -n  
10.           
11.         while t > 0:  
12.             a.append(t % 2)  
13.             t = t >> 1  
14.         for i in range(1,len(a)+1):  
15.             result = result * result * (1 if a[-i] == 0 else x)  
16.           
17.         if n <0 : result = 1.0 / result  
18.         return result  

class Solution:
    # @param {float} x
    # @param {integer} n
    # @return {float}
    def myPow(self, x, n):
        if n == 0: return 1
        result = 1
        a = []
        t = n if n>0 else -n
        
        while t > 0:
            a.append(t % 2)
            t = t >> 1
        for i in range(1,len(a)+1):
            result = result * result * (1 if a[-i] == 0 else x)
        
        if n <0 : result = 1.0 / result
        return result

III. Non-recursive Solution - O(log n) time - O(1) space
This is an improvement on the solution numbered II.

view plainprint?

1. class Solution:  
2.     # @param {float} x  
3.     # @param {integer} n  
4.     # @return {float}  
5.     def myPow(self, x, n):  
6.         if n == 0: return 1  
7.         m = n  
8.         if n < 0:  
9.             m = -m  
10.             x = 1/x  
11.           
12.         result = 1  
13.         while m > 0:  
14.               
15.             if (m & 1) == 1:  
16.                 result *= x  
17.             x *= x  
18.             m >>=1  
19.               
20.         return result    

class Solution:
    # @param {float} x
    # @param {integer} n
    # @return {float}
    def myPow(self, x, n):
        if n == 0: return 1
        m = n
        if n < 0:
            m = -m
            x = 1/x
        
        result = 1
        while m > 0:
            
            if (m & 1) == 1:
                result *= x
            x *= x
            m >>=1
            
        return result