JZ16 数值的整数次方

发表于 分类于 本文字数： 430 阅读时长 ≈ 2 分钟

JZ16 数值的整数次方

描述

实现函数 double Power(double base, int exponent)，求base的exponent次方。

注意：

1.保证base和exponent不同时为0。

2.不得使用库函数，同时不需要考虑大数问题

3.有特殊判题，不用考虑小数点后面0的位数。

数据范围： $∣base∣≤100 $ ， $∣exponent∣≤100 $ ,保证最终结果一定满足 $∣val∣≤104 $
进阶：空间复杂度 $O(1)$ ，时间复杂度 $O(n)$

示例1

1
2
输入：2.00000,3
返回值：8.00000

示例2

1
2
输入：2.10000,3
返回值：9.26100

示例3

1
2
3
输入：2.00000,-2
返回值：0.25000
说明：2的-2次方等于1/4=0.25

题解

一开始我考虑的是完全使用位运算，把问题想复杂了。看了一下讨论，学习到了一个叫快速幂的思想。

快速幂：求$A^n$，可以求$A^2$,借由此继续求$A^4$直到$A^n(n为偶数)，或A^{n-1}(n为奇数)$。

具体到本题的实现就是首先判断负数次方（取倒数），然后用位运算做快速幂即可。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#
# @param base double浮点型
# @param exponent int整型
# @return double浮点型
#


class Solution:
    # 快速幂
    def Pow(self, x: float, y: int) -> float:
        res = 1
        while y:
            # 判断是不是奇数，可以再往上乘一个
            if y & 1:  # y的最后1位是0，结果就是false，最后一位是1，结果为true
                res *= x
            # x叠加
            x *= x
            # 减少乘次数，如果是奇数右移，会在除2的基础上减一，偶数就是直接除2
            y = y >> 1
        return res

    def Power(self, base: float, exponent: int) -> float:
        # 处理负数次方
        a = 7  # 1111,右移两位，为11
        print(a >> 1)
        if exponent < 0:
            base = 1 / base
            exponent = -exponent
        res = 1.0
        return self.Pow(base, exponent)