Meta Pow：快速幂、负指数与数值边界

题目重点：通过指数二进制分解加速乘方，处理负指数、零底数和固定宽度取反。

题意与假设

这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。

训练实数base、整数exponent，0^0选择1，0的负指数报错；浮点输出有误差，不保证任意大幂有限。具体数值合同与输出误差需要练习前确认。

解题路线

先把负指数转倒数底数和非负指数，随后循环每轮若指数最低位1就result乘当前base，再平方base、指数除2。
循环不变量result×base^remaining等于原目标。处理奇数位分出一个base后remaining减少1，平方和除2不改余下乘方意义；剩余0时result即答案。
只做O(log|n|)轮，区别逐次乘n遍。递归也可每次只计算half一次，再平方，不能同层递归调用两次相同half，否则退回线性。
固定宽度语言exponent=最小负整数时直接−n会溢出，先扩更宽类型或处理无符号绝对值。Python整数无该固定宽度溢出，不能因此忽略跨语言边界。
浮点上溢/下溢和误差是数值表现，不是语法错误；如果要求modular power或任意精度，接口和运算成本不同。

手动走一遍

2^13按13二进制1101，通过2、4、16、256的平方链取2×16×256=8192。2^−3=1/8，指数0为1；0^−1不能求倒数。

Python 参考实现

下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。

代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。

def power(base,exponent):
    """Integer exponent, real base; 0**0=1, zero negative power raises."""
    if not isinstance(exponent,int):raise TypeError('integer exponent')
    if exponent<0:
        if base==0:raise ZeroDivisionError('zero negative power')
        base=1/base;exponent=-exponent
    result=1
    while exponent:
        if exponent&1:result*=base
        base*=base;exponent//=2
    return result

复杂度

O(log(|n|+1))次乘法、O(1)迭代状态，按固定精度运算计。任意精度整数结果位数随指数增长，乘法不能按常数计；递归版本另有O(log|n|)栈。

易错点与追问

容易失分的边界

递归同一half两次导致复杂度增长。
固定宽度最小负数取反溢出。

继续深挖

模幂可每次乘后取mod控制位数，负指数则需模逆存在条件。
为何浮点实现与库pow未必bitwise相同？乘法顺序不同导致舍入。