12 数值的整数次方

题目描述

给定一个double类型的浮点数base和int类型的整数exponent。求base的exponent次方。不得使用库函数，同时不需要考虑大数问题。

示例：

输入: base=2, exponent=3, 输出: 8
输入: base=2, exponent=-3, 输出: 0.125
输入: base=0, exponent=-1, 输出: 0 (非法输入)

解题思路

核心思想：使用快速幂算法。

关键步骤：

1. 处理特殊情况：base为0且exponent为负数，返回0
2. 计算exponent的绝对值的幂
3. 如果exponent为负数，取倒数

快速幂算法：

• 偶数次方：n^k = (n^(k/2))^2
• 奇数次方：n^k = n * n^(k-1)

时间复杂度：O(log n) 空间复杂度：O(log n)（递归）或 O(1)（迭代）

Python 实现

def power(base, exponent):
    """
    计算base的exponent次方

    Args:
        base: 底数
        exponent: 指数

    Returns:
        float: base的exponent次方
    """
    # 处理特殊情况
    if base == 0 and exponent < 0:
        return 0

    abs_exponent = abs(exponent)
    result = power_unsigned(base, abs_exponent)

    # 处理负指数
    if exponent < 0:
        result = 1 / result

    return result


def power_unsigned(base, exponent):
    """
    快速幂算法（非负指数）
    """
    if exponent == 0:
        return 1
    if exponent == 1:
        return base

    result = power_unsigned(base, exponent >> 1)
    result *= result

    # 如果是奇数，再乘一次base
    if exponent & 1:
        result *= base

    return result


# 迭代版本
def power_iterative(base, exponent):
    """
    迭代版本快速幂
    """
    if base == 0 and exponent < 0:
        return 0

    abs_exponent = abs(exponent)
    result = 1.0
    current_base = base

    while abs_exponent > 0:
        if abs_exponent & 1:
            result *= current_base
        current_base *= current_base
        abs_exponent >>= 1

    if exponent < 0:
        result = 1 / result

    return result


# 测试代码
if __name__ == "__main__":
    test_cases = [
        (2, 3),
        (2, -3),
        (0, -1),
        (3, 0),
        (-2, 3),
    ]

    for base, exp in test_cases:
        print(f"{base}^{exp} = {power(base, exp)}")

# 输出:
# 2^3 = 8.0
# 2^-3 = 0.125
# 0^-1 = 0.0
# 3^0 = 1.0
# -2^3 = -8.0

图解

快速幂算法示例: 计算 2^10

分解过程:
2^10 = (2^5)^2
2^5  = 2 * (2^2)^2
2^2  = (2^1)^2
2^1  = 2

回溯:
power(2, 1) = 2
power(2, 2) = power(2, 1)^2 = 4
power(2, 5) = 2 * power(2, 2)^2 = 2 * 16 = 32
power(2, 10) = power(2, 5)^2 = 1024

二进制视角: 2^10 = 2^(1010)
result = 1
1010的第3位是1 → result *= 2^8 = 256
1010的第1位是1 → result *= 2^2 = 1024