剑指 数值的整数次方

快速幂，分奇数偶数讨论，指数分正负讨论，当指数为负数时需要将底数变为倒数进行求解。
注意判断条件 0为底数时，指数为0或负无意义，如果指数为正 则结果为0.
求出的幂结果实际上就是在变化过程中所有当指数为奇数时底数的乘积。
空间logn
时间logn

# -*- coding:utf-8 -*-
class Solution:
    def Power(self, base, exponent):
        # write code here
       if base==0 and exponent<=0:
            return    None
       if base==0 and exponent>0:
            return 0
       if exponent<0:
            exponent=-exponent
            base=1/base
       if exponent==0:
            return 1
       n=exponent//2
       temp=self.Power(base, n)
       if exponent%2==0:
          return temp*temp
       else:
          return temp*temp*base

迭代的方法 注意判断条件 0为底数时，指数为0或负无意义，如果指数为正 则结果为0.
算法流程：
当 x = 0 时：直接返回 0 （避免后续 x=1/x 操作报错）。
初始化 res = 1；
当 n < 0时：把问题转化至 n>0 的范围内，即执行 x=1/x ，n=−n ；
循环计算：当 n = 0时跳出；
当 n&1=1 时：将当前 x 乘入 res （即 res∗=x ）；
执行 x = x^2 （即 x∗=x ）；
执行 n右移一位（即n>>=1）。
返回 res。

按照把指数分解成二进制进而 思考 比较方便
每次n&1判断最右边的位置是否为1 如果是1则结果*当前的base值 由于二进制的特点，1，2，4，8... 每次循环base都需要乘方，方便在最右位置为1 时可以乘到结果中，如果最右位置不是1 则可以继续准备base的值。n>>1 当最右位置判断完毕，可以右移掉。当 n为0 也就是为1的位都被移掉了，就结束。

令循环体为x∗=x，n>>=1
循环1次可以得到x ^ 2循环1次可以得到x^2
循环2次的时候n为奇数，把这个x ^ 2 乘到结果中
循环4次可以得到 x ^ {16}
循环5次的时候n为奇数，把x ^ {16}乘到结果中
也就是n的二进制数中有几个1就会乘几次，且乘数在循环中一次一次倍增

时间logn
空间1

# -*- coding:utf-8 -*-
class Solution:
    def Power(self, base, exponent):
        # write code here
        result=1
        if base==0 and exponent<=0:
            return None
        if base==0:
            return 0

        if exponent<0:
            exponent=-exponent
            base=1/base
        while exponent>0:
            if exponent&1!=0:
                result*=base

            base=base*base
            exponent=exponent>>1

        return result

向下整除 n // 2n//2 等价于 右移一位 n >> 1n>>1 ；
取余数 n % 2n%2 等价于 判断二进制最右一位值 n & 1n&1 ；
改为位运算好理解，同时加速