京公网安备11010502063487号实现 pow(x, n)：计算浮点数 x 的整数 n 次方，n 可能是负数。逐个相乘要 n 次乘法，n 最大到 21 亿，太慢。快速幂的思路是把 n 写成二进制：x 的 n 次方等于若干个 x 的 2^k 次方的乘积，其中 k 是 n 的二进制里为 1 的那些位；而 x 的 2^k 次方可以由前一个不断平方得到。这样只需要约 31 次乘法。这道题还有一个隐蔽的坑：n 可能是 -2147483648，直接取相反数会溢出。本文用真实的 Java 程序展示这个溢出，实测快速幂与逐个相乘的耗时，给出五种语言的实现，并把二进制分解做成分步演示。
完整题目见官方页面（链接在文末）。结果是浮点数，所以核对时不要求逐位相同。基准解是 Python 内置的浮点数幂运算 x ** n。测试程序里 Java、JavaScript、C++ 按 5 位小数输出，所以比较标准是"相对误差 1e-9 或绝对误差 1e-5"。一共 18 组用例，覆盖：官方示例、负指数、指数为 0、底数为负、以及 n 取 32 位整数两端的 2147483647 和 -2147483648：
输入 [2.0,10] 输出 1024.0 输入 [2.1,3] 输出 9.261000000000001 输入 [2.0,-2] 输出 0.25 输入 [1.0,2147483647] 输出 1.0 输入 [1.0,-2147483648] 输出 1.0 输入 [-1.0,2147483647] 输出 -1.0
处理负指数的常见写法是：n < 0 时令 x = 1 / x、n = -n。但 32 位有符号整数的最小值 -2147483648 取相反数应该是 2147483648，比最大值 2147483647 还大 1，放不进 32 位。下面是真实运行的 Java 程序：
指数 n = -2147483648 时，`n = -n` 会怎样： Java: -Integer.MIN_VALUE = -2147483648（还是负的） Java: 先转成 long 再取负 = 2147483648 Python: solve(2.0, -2147483648) = 0.0，solve(1.0, -2147483648) = 1.0，solve(-1.0, -2147483648) = 1.0
Java 里 -Integer.MIN_VALUE 得到的还是 -2147483648，仍然是负数，后面的 while (n > 0) 一次都不执行，永远返回 1。解决办法是先把指数转成 long（Java）、long long（C++）、int64（Go）再取相反数。Python 的整数不会溢出，JavaScript 的数字是双精度浮点，-2147483648 取相反数也是精确的，所以这两种语言不需要特殊处理。用例里有 (2.0, -2147483648)，结果应该是趋近于 0 的很小的数，5 位小数下是 0.0，(-1.0, -2147483648) 和 (1.0, -2147483648) 应该是 1。
每一轮看 n 的最低位：是 1 就把当前的 x 乘进结果；然后 x 自乘（x、x²、x⁴、x⁸……依次翻倍），n 右移一位。n 为 0 时结束。负指数先转成 1/x 的正指数。JavaScript 的位运算只有 32 位，所以用 n % 2 和 Math.floor(n / 2) 代替 n & 1 和 n >> 1。Python、Java、Go、JavaScript、C++ 都是真实编译运行的。
Python · 解法代码def solve(x, n): if n < 0: # 负指数：x^n = (1/x)^(-n)。-n 在 32 位整数下可能溢出，所以别的语言里要先转 long x, n = 1 / x, -n result = 1.0 while n: if n & 1: # 二进制的这一位是 1：把当前的 x 乘进结果 result *= x x *= x # x 依次变成 x, x^2, x^4, x^8 ... n >>= 1 return result
$ python3 solution.py # 统一入口：逐行读取 cases.jsonl，调用上面的 solve，打印 JSON [2.0,10] → 1024.0 [2.1,3] → 9.261000000000001 [2.0,-2] → 0.25 [1.0,2147483647] → 1.0 [1.0,-2147483648] → 1.0 [-1.0,2147483647] → -1.0
Java · 解法代码class Solution { public double myPow(double x, int n) { long e = n; // 先转成 long：-Integer.MIN_VALUE 在 int 里会溢出 if (e < 0) { x = 1 / x; e = -e; } double result = 1.0; while (e > 0) { if ((e & 1) == 1) result *= x; // 二进制的这一位是 1：把当前的 x 乘进结果 x *= x; // x 依次变成 x, x^2, x^4, x^8 ... e >>= 1; } return result; } }
$ javac -d build Main.java Solution.java && java -cp build Main < cases.jsonl [2.0,10] → 1024.00000 [2.1,3] → 9.26100 [2.0,-2] → 0.25000 [1.0,2147483647] → 1.00000 [1.0,-2147483648] → 1.00000 [-1.0,2147483647] → -1.00000
Go · 解法代码func myPow(x float64, n int) float64 { e := int64(n) // 转成 int64，避免 -n 在 32 位下溢出 if e < 0 { x = 1 / x e = -e } result := 1.0 for e > 0 { if e&1 == 1 { // 二进制的这一位是 1：把当前的 x 乘进结果 result *= x } x *= x // x 依次变成 x, x^2, x^4, x^8 ... e >>= 1 } return result }
$ go build -o bin . && ./bin < cases.jsonl [2.0,10] → 1024 [2.1,3] → 9.261000000000001 [2.0,-2] → 0.25 [1.0,2147483647] → 1 [1.0,-2147483648] → 1 [-1.0,2147483647] → -1
JavaScript · 解法代码function myPow(x, n) { if (n < 0) { // 负指数：x^n = (1/x)^(-n)（JS 数字是双精度，-n 不会溢出） x = 1 / x; n = -n; } let result = 1.0; while (n > 0) { if (n % 2 === 1) result *= x; // 二进制的这一位是 1：把当前的 x 乘进结果（不用 &，它只有 32 位） x *= x; // x 依次变成 x, x^2, x^4, x^8 ... n = Math.floor(n / 2); } return result; }
$ node run.js < cases.jsonl [2.0,10] → 1024 [2.1,3] → 9.26100 [2.0,-2] → 0.25000 [1.0,2147483647] → 1 [1.0,-2147483648] → 1 [-1.0,2147483647] → -1
C++ · 解法代码using namespace std; class Solution { public: double myPow(double x, int n) { long long e = n; // 先转成 long long：-INT_MIN 在 int 里会溢出 if (e < 0) { x = 1 / x; e = -e; } double result = 1.0; while (e > 0) { if (e & 1) result *= x; // 二进制的这一位是 1：把当前的 x 乘进结果 x *= x; // x 依次变成 x, x^2, x^4, x^8 ... e >>= 1; } return result; } };
$ clang++ -std=c++17 -O2 -o bin sol.cpp && ./bin < cases.jsonl [2.0,10] → 1024.00000 [2.1,3] → 9.26100 [2.0,-2] → 0.25000 [1.0,2147483647] → 1.00000 [1.0,-2147483648] → 1.00000 [-1.0,2147483647] → -1.00000
共 18 组用例（含边界），以暴力解的结果为基准逐组比对： Python 通过 18/18 Java 通过 18/18 Go 通过 18/18 JavaScript 通过 18/18 C++ 通过 18/18
底数取 1.0000001（这样结果不会溢出，n = 1000 万时结果约等于 e），逐个相乘 n 次，与快速幂对比，每个取三次中最快的一次：
底数 1.0000001，指数 n：逐个相乘（n 次乘法）vs 快速幂（约 31 次乘法）——每个取三次中最快 n= 100000: 逐个相乘 1.648 ms（结果 1.0100501666） 快速幂 0.0010 ms（结果 1.0100501666） n= 1000000: 逐个相乘 16.763 ms（结果 1.1051709126） 快速幂 0.0010 ms（结果 1.1051709126） n= 10000000: 逐个相乘 170.226 ms（结果 2.7182816941） 快速幂 0.0014 ms（结果 2.7182816940）
逐个相乘的耗时与 n 成正比：10 万次 1.65ms，100 万次 16.6ms，1000 万次 168.8ms；快速幂只需要约 31 次乘法，耗时都是 0.001 毫秒量级，几乎不随 n 变化。两种做法结果的前 9 位小数一致，n = 1000 万时最后一位（第 10 位小数）差了一点（2.7182816941 对 2.7182816940），这是浮点数乘法次数不同导致的累积舍入误差，在题目要求的精度内可以忽略。n = 21 亿时逐个相乘要几十秒，没有运行。
Python 版本另外和内置的 x ** n 做了随机对拍，底数取 -3 到 3 的两位小数（非 0），指数取 -25 到 25：
随机对拍 20000 组（底数取 -3 到 3 的两位小数（非 0），指数取 -25 到 25；浮点数按「相对误差 1e-9 或绝对误差 1e-5」比较），solve 与 brute 的结果全部一致。
另外四种语言只在上面 18 组固定用例上验证过，没有做大规模随机对拍。
下面的演示用 3 的 13 次方。13 的二进制是 1101，从低位到高位是 1、0、1、1：第 0 位是 1，把 3 乘进结果；第 1 位是 0，不乘；第 2 位是 1，此时 base 已经是 3⁴ = 81，结果变成 3 × 81 = 243；第 3 位是 1，base 是 3⁸ = 6561，结果变成 243 × 6561 = 1594323。只用了 4 轮循环就得到了 3¹³。每一帧都是把上面的解法在这组输入上真实执行记录下来的，运行器还检查了演示的最终结果与 solve 的返回值一致。