剑指 Offer16-数值的整数次方

兴趣爱好交流 每日一题
1

剑指Offer16-数值的整数次方

实现 pow(x, n) ，即计算 x 的 n 次幂函数（即，xn）。不得使用库函数，同时不需要考虑大数问题。

示例 1：


输入：x = 2.00000, n = 10

输出：1024.00000

示例 2：


输入：x = 2.10000, n = 3

输出：9.26100

示例 3：


输入：x = 2.00000, n = -2

输出：0.25000

解释：2-2 = 1/22 = 1/4 = 0.25

提示：

-100.0 < x < 100.0

-2^(31) <= n <= 2^(31)-1

-10^4 <= x^n <= 10^4

来源：力扣（LeetCode）

链接：力扣

一解

使用快速幂解决：

828×90 4 KB

将上述运算用符号表示：

864×142 5.76 KB

由于 bi 有0和1两种情况：

当bi = 0时：

x2ibi = 1

当bi = 1时：

x2ibi = x2i


class Solution:

    def myPow(self, x: float, n: int) -> float:

        if x == 0:

            return 0

        # n < 0 时，x^-2 = (1/x)^2

        if n < 0:

            n, x = -n, 1/x

        res = 1

        while n:

            # 判断二进制最右面的数是否为 1

            if n & 1:

                 # x^(2^i)

                res *= x

            # x^(2^(i+1))

            x *= x

            # 右移一位

            n >>= 1

        return res

很多人不理解，快速幂快在哪里?

下面的算法，要进行n次运算，而快速幂只需要n的二进制的长度次：

比如9876：

  • 普通算法：9876次

  • 快速幂：9876 → 10 0110 1001 0100（二进制），长度为14，计算14次


class Solution:

    def myPow(self, x: float, n: int) -> float:

        if n < 0:

            n, x = -n, 1/x

        result = 1

        while n != 0:

            result *= x

            n -= 1

        return result
1 个赞
2 
import time
from functools import wraps


def timethis(func):
    @wraps(func)
    def wrapper(*args, **kwargs):
        start = time.time()
        result = func(*args, **kwargs)
        end = time.time()
        print(f"func {func.__name__} run {end - start} s")
        return result

    return wrapper


class Solution:

    @timethis
    def myPow(self, x: float, n: int) -> float:
        if x == 0:
            return 0
        # n < 0 时，x^-2 = (1/x)^2
        if n < 0:
            n, x = -n, 1 / x
        res = 1
        while n:
            # 判断二进制最右面的数是否为 1
            if n & 1:
                # x^(2^i)
                res *= x
            # x^(2^(i+1))
            x *= x
            # 右移一位
            n >>= 1
        return res


print(Solution().myPow(22, 500))


@timethis
def my_pow(x: float, n: int) -> float:
    if x == 0:
        return 0
    if n < 0:
        x, n = 1 / x, -n
    elif n == 0:
        return 1
    else:
        res = 1
        while n > 0:
            res *= x
            n -= 1
        return res


print(my_pow(22, 500))

这个比正常乘积快很多，应该数值越大越明显

func myPow run 1.6927719116210938e-05 s
162682340185280589684399673739785336375464574929263083585020771269597641831590836674610436789332474924071305129427327247893917148681006208568781193983328435209736520891570695193808702178081883775191857370045854699638255840761178047937534795398619179991734821370147275102175630623780378929380280957610636947404398456796904514361070431673380738436551665305817580663310264776564510905087403380320860030247314634374797327243866439609828825321528550916862229724645348080285831007224322697120912040419898692902360077248415336302479967871146438553740502543845353859715671396462388844772002496955199206462308455849823195683382036430621297380424060001784641049649781081395876069376
func my_pow run 0.00012421607971191406 s
162682340185280589684399673739785336375464574929263083585020771269597641831590836674610436789332474924071305129427327247893917148681006208568781193983328435209736520891570695193808702178081883775191857370045854699638255840761178047937534795398619179991734821370147275102175630623780378929380280957610636947404398456796904514361070431673380738436551665305817580663310264776564510905087403380320860030247314634374797327243866439609828825321528550916862229724645348080285831007224322697120912040419898692902360077248415336302479967871146438553740502543845353859715671396462388844772002496955199206462308455849823195683382036430621297380424060001784641049649781081395876069376
3

快速幂计算吗？ 但是实际运行发现没比直接计算快多少额？为什么？

def pow(x,n):
    if n==0:
        return 1
    elif n<0:
        return 1/pow(x,-n)
    elif n%2==1:
        return x*pow(x,n-1)
    else:
        return pow(x*x,n//2)
5

你这个跑不通： 2.00000 -2

6

考虑这个输入：

2.00000 -2147483648

7 
def my_pow(x: float, n: int) -> float:
    if x == 0:
        return 0
    if n < 0:
        x, n = 1 / x, -n
    elif n == 0:
        return 1
    res = 1
    while n > 0:
        res *= x
        n -= 1
    return res

确实，多谢指正，逻辑有错误