class Solution:

    #递归思路

    def myPow_recursion(self,x,n):

        if n == 0:                                  #递归终止条件，n==0返回1

            return 1

        if n < 0:                                   #n小于0，就返回其倒数，-n和其递归结构一致

            return 1 / self.myPow_recursion(x,-n)

        if n & 1:                                   #判断是奇数，则结果为x*（x的n-1次方）

            return x * self.myPow_recursion(x,n-1)

        else:                                       #判断是偶数，则结果是x的平方*x的n/2次方

            return self.myPow_recursion(x*x,n/2)

    #非递归思路

    def myPow_loop(self,x,n):

        if n < 0:                                   #如果n小于0，则为n变为正数，值为其倒数

            n = -n

            x = 1 / x

        pow = 1                                     #结果值初始为1

        while n:                                    #遍历循环，是n一直除以2

            if n & 1:                               #奇数时候

                pow *= x                            #pow是x

            x *= x                                  #x乘以x

            n >>= 1                                 #n连续性的除以2

        return pow

if __name__ == '__main__':

    solution = Solution()

    #(2,-1) (2,0) (2,2) (2,5)

    x,n = 2,-2

    result = solution.myPow_recursion(x,n)

    print(result)

    result = solution.myPow_loop(x,n)

    print(result)