面试题16：数值的整数次方

从乘 13 次能否只做几次乘法开始

先预测：直接计算x^13需要连续乘12次；若先得到x^6，平方得到x^12再乘x，而x^6又可由x^3平方得到，指数经历13→6→3→1。工作量为什么随指数位数而不是指数本身增长？——这就是快速幂。

“数值的整数次方”要求实现Power(double base, int exponent)，不能调用库幂函数。除了效率，真正考点是把输入分类：正指数、零指数、负指数，正负底数，以及底数为0的边界。

对非零底数，整数次幂可定义为：

先于算法。0的正指数为0，作者约定0^0=1，而0的负指数需要除以0，应报告非法输入。若不先锁定这些规则，快速幂循环再正确也无法决定返回什么。

递归快速幂只求一次半次幂

利用指数奇偶性：

重点是半次幂只递归计算一次，保存后平方。若写成power(x,n/2) * power(x,n/2)，两棵相同递归树会把复杂度重新扩大。每层指数右移一位，递归深度和乘法次数都是O(log |n|)。

的无符号核心如下：

#include <cstdint>
 
double powerUnsignedRecursive(double base,
                              std::uint64_t exponent) {
    if (exponent == 0) return 1.0;
    if (exponent == 1) return base;
 
    double half = powerUnsignedRecursive(base, exponent >> 1U);
    double result = half * half;
    if ((exponent & 1U) != 0) result *= base;
    return result;
}
 
struct PowerResult {
    double value;
    bool valid;
};
 
PowerResult powerRecursive(double base, std::int32_t exponent) {
    if (base == 0.0 && exponent < 0) {
        return {0.0, false};
    }
 
    const auto wideExponent = static_cast<std::int64_t>(exponent);
    const std::uint64_t magnitude =
        wideExponent < 0
            ? static_cast<std::uint64_t>(-wideExponent)
            : static_cast<std::uint64_t>(wideExponent);
 
    double value = powerUnsignedRecursive(base, magnitude);
    if (exponent < 0) value = 1.0 / value;
    return {value, true};
}

先把32位指数提升到64位有符号数，再取负，避免最小32位整数取反溢出。得到的可放入uint64_t；核心不再关心负指数，包装层最后统一取倒数。

迭代版按指数二进制位选择因子

任何非负指数都可展开为二进制位：

迭代版维护factor=x^(2^i)。当前最低位为1就把factor乘入结果；随后factor平方，指数右移，进入下一二进制位。指数13是1101₂，选择x、x^4、x^8，乘积为x^13。

PowerResult powerIterative(double base, std::int32_t exponent) {
    if (base == 0.0 && exponent < 0) {
        return {0.0, false};
    }
 
    const auto wideExponent = static_cast<std::int64_t>(exponent);
    std::uint64_t remaining =
        wideExponent < 0
            ? static_cast<std::uint64_t>(-wideExponent)
            : static_cast<std::uint64_t>(wideExponent);
 
    double result = 1.0;
    double factor = base;
    while (remaining != 0) {
        if ((remaining & 1U) != 0) {
            result *= factor;
        }
        remaining >>= 1U;
        if (remaining != 0) {
            factor *= factor;
        }
    }
 
    if (exponent < 0) result = 1.0 / result;
    return {result, true};
}

循环中的可写为：

处理最低位后，若该位为1就把一个factor移到result；指数除2、因子平方后等式仍成立。终止时remaining=0，右侧待处理因子为1，因此result=x^{|n|}。迭代版时间O(log |n|)、额外空间O(1)，递归版栈空间O(log |n|)。

负指数与最小整数陷阱

负指数不是在循环中不断乘倒数最清晰，而是先对|n|执行同一个无符号核心，再取一次倒数。这样奇偶分支、复杂度和测试都只维护一份。

作者源码先在int上计算-exponent。当exponent=INT_MIN时，其正值超出int最大范围，有符号溢出是未定义行为。先强转无符号再取反也容易得到意外语义；提升到更宽的int64_t后再取负，才覆盖整个32位输入域。

负底数的符号无需特判。偶指数的二进制乘法最终得到正数，奇指数多乘一次负底数得到负数；负指数取倒数不会改变符号奇偶规律。额外分支反而可能让-0.0、无穷等浮点值处理不一致。

底数为 0 的边界与浮点比较

作者用绝对误差1e-7判断底数是否“等于0”，再拒绝负指数。这会把1e-8这样的非零底数误判为零，尽管它的负次幂在浮点范围内可能有定义。定义域判断应使用base == 0.0，它同时识别正零和负零；近似比较只用于验证计算结果。

要求测试同时考虑绝对误差和相对误差。接近0时绝对误差有意义，数值很大时应按结果规模放宽；不能用同一个固定 epsilon 同时比较1e-12和1e100。

作者把0^0约定为1，因为无符号核心指数0返回乘法单位元1。数学文献对0^0语境不同可能有不同约定，API 必须明确；本页忠实采用作者测试。0的正指数自然通过乘法得到0，只有零底数负指数返回非法状态。

错误状态不应藏在全局变量里

作者使用全局g_InvalidInput区分合法结果0与非法输入。每次入口虽先清零，但全局状态不是线程安全的，调用者还可能忘记在读取返回值后同步检查标志。返回PowerResult、optional<double>或expected<double,Error>能把值和状态绑定在一次调用结果中。

错误与浮点上溢也应区分。2^2000可能得到正无穷，极小底数大正指数可能下溢到0；这不是零底数负指数的定义域错误，而是double表示范围问题。接口可以允许 IEEE 754 无穷/零，也可以用isfinite检测并报告数值范围错误，但不能都压成同一个布尔标志。

NaN 输入会传播 NaN；正负无穷遵循浮点乘法和倒数规则。原题明确“不需要考虑大数问题”，面试实现可不扩展这些状态，但工程文档应说明采用平台浮点语义还是主动拒绝非有限输入。

乘法顺序会影响浮点近似

实数乘法满足结合律，但有限精度浮点每次乘法后都舍入，(a·b)·c与a·(b·c)可能差几个末位。朴素连续乘、递归平方和二进制迭代的乘法顺序不同，因此结果不保证逐位相同；测试应比较容差或 ULP，而不是要求所有实现的double位模式一致。

平方还可能更早上溢。比如因子已经很大时factor *= factor先得到无穷，即使某些后续数学组合在扩展精度中仍可表达；负指数则可能先算出巨大正次幂为无穷，再取倒数成为0。另一种做法是先把底数取倒数再计算正指数，它可能改成逐步下溢。两者都受double范围限制，只是舍入路径不同。

若需求强调数值稳定性，可使用更宽浮点类型、中途缩放并记录指数、对数域计算，或调用经过验证的数学库。算法题的O(log n)乘法次数说明性能，不自动提供最小误差；“更少乘法”通常减少舍入机会，但平方会放大已有相对误差。

整数模幂则没有浮点近似问题，但必须在每次乘法后取模并防止中间乘积溢出。它复用相同二进制指数框架，却属于不同数值域；不能把double版本简单强转成整数后声称支持密码学模幂。

用指数律做性质测试

除官方固定样例外，可在安全数值范围随机生成x、a、b，检查power(x,a+b)近似等于power(x,a)·power(x,b)；对非零x检查power(x,-a)·power(x,a)近似为1；对偶指数检查power(-x,2a)与power(x,2a)相等。

性质测试的前置条件必须过滤指数相加溢出、零底数负指数、结果非有限和严重下溢。若一边已经是无穷、另一边是0·∞得到 NaN，指数律在实数上成立也不能直接转换成浮点断言。先限制|x|与指数范围，才能让失败更可能指向算法而非表示范围。

还可以记录实际乘法次数：无符号指数为0时0次，非零指数每处理一个二进制位最多一次平方，每个1位最多一次乘入结果。次数应随bit_width(n)增长，而不随n线性增长；这能发现误把快速幂写成循环乘n次的性能回归。

递归与迭代实现互为结构不同的预言机，但两者可能共享绝对值转换错误，所以INT_MIN必须单独断言。固定样例、代数性质、乘法计数和标准库参考共同组成比单一结果表更强的验证。

官方七组测试覆盖输入分类

作者测试2^3=8、(-2)^3=-8、2^-3=0.125、2^0=1、0^0=1、0^4=0，以及0^-4返回0并设置非法标志。它们覆盖符号、倒数、零指数和定义域错误。

现代测试还应加入负底数偶指数、指数1与INT_MIN、极小非零底数，以及递归/迭代对随机安全范围输入的交叉验证。结果预言机可使用std::pow，但被测实现本身不能调用它。

#include <algorithm>
#include <cassert>
#include <cmath>
#include <cstdint>
#include <limits>
 
bool nearlyEqual(double actual, double expected) {
    const double difference = std::abs(actual - expected);
    const double scale = std::max(
        {1.0, std::abs(actual), std::abs(expected)});
    return difference <= 1e-12 * scale;
}
 
void testPower() {
    const struct {
        double base;
        std::int32_t exponent;
        double expected;
        bool valid;
    } cases[] = {
        {2.0, 3, 8.0, true},
        {-2.0, 3, -8.0, true},
        {2.0, -3, 0.125, true},
        {2.0, 0, 1.0, true},
        {0.0, 0, 1.0, true},
        {0.0, 4, 0.0, true},
        {0.0, -4, 0.0, false},
    };
 
    for (const auto& test : cases) {
        const auto recursive =
            powerRecursive(test.base, test.exponent);
        const auto iterative =
            powerIterative(test.base, test.exponent);
        assert(recursive.valid == test.valid);
        assert(iterative.valid == test.valid);
        if (test.valid) {
            assert(nearlyEqual(recursive.value, test.expected));
            assert(nearlyEqual(iterative.value, test.expected));
        }
    }
 
    const auto minimumExponent = powerIterative(
        1.0, std::numeric_limits<std::int32_t>::min());
    assert(minimumExponent.valid);
    assert(minimumExponent.value == 1.0);
}

这里nearlyEqual只在状态合法时比较值；非法用例不要求伪返回值等于某个数。若先只比较0再检查错误标志，合法的0^4和非法的0^-4容易被测试混在一起。

本章练习

本章回顾

1. 数值的整数次方先按指数符号和零底数确定定义域。
2. 快速幂利用偶次平方、奇次平方后乘底数，把时间降为O(log |n|)。
3. 递归版栈空间O(log |n|)，迭代二进制版额外空间O(1)。
4. 负指数先计算指数绝对值次幂，再取一次倒数。
5. INT_MIN不能在32位int中直接取负，必须先提升到更宽类型。
6. 底数是否为零属于定义域判断，应精确比较；epsilon只用于近似结果测试。
7. 作者约定0^0=1，0的负指数通过显式错误状态报告。
8. 全局错误标志应替换为携带值与状态的返回类型，便于线程安全和完整测试。

名词解释