剑指Offer编程题-数值的整数次方 | 我的个人生活记录

题目：数值的整数次方

题目描述：给定一个double类型的浮点数base和int类型的整数exponent。求base的exponent次方。

解题思路

假设求a^n，一般的想法是用循环将a乘n次，这样的时间复杂度是O(n)，但是使用快速幂的方法可以将复杂度降到O(log2(n))。

快速幂：假设n=13，我们求a^13，n的二进制表示为1101，即2^3 + 2^2 +2^1，那么a^13 = a^(2^3 + 2^2 +2^1) = a^(2^3)*a^(2^2)*a^(2^1)。通过>>移位以及&1运算可以用来判断二进制每一位是否为1，我们先初始化一个变量m = 1，用来保存结果，在判断n的二进制位为1时，m *= a，然后n右移一位并且a *= a直到n为0。

除了移位，也可以根据10进制转2进制的原理，通过对2求余来迭代，并判断余数是否为1

实现

python

方法1:

# -*- coding:utf-8 -*-
class Solution:
    def Power(self, base, exponent):
        # write code here
        e = 1
        a = 1
        if exponent < 0:
            exponent = -exponent
            e = -1
        while exponent:
            if exponent&1:
                a *= base
            base *= base
            exponent >>= 1
        return a if e>0 else 1/a

python

方法2:

class Solution:
    def Power(self, base, exponent):
        # write code here
        e = 1
        a = 1
        if exponent < 0:
            exponent = -exponent
            e = -1
        while exponent:
            if exponent%2:
                a *= base
            base *= base
            exponent  = int(exponent/2)
        return a if e>0 else 1/a