力扣第 50 题Pow(x, n)

力扣第 50 题是 Pow(x, n)，要求实现一个计算 x 的 n 次幂的函数，即实现函数 double myPow(double x, int n)。这个问题考察的是如何在高效的情况下计算大次幂，尤其是如何处理 n 为负数的情况。

解题思路

如果 n 是负数，将问题转化为求 1 / myPow(x, -n)，并且注意处理 n 为最小值的情况。
使用递归实现快速幂运算，如果 n 为偶数，则计算 myPow(x, n / 2) * myPow(x, n / 2)；如果 n 为奇数，则计算 x * myPow(x, n / 2) * myPow(x, n / 2)。
优化的迭代解法通过位运算实现快速幂，避免了递归的函数开销。

代码实现

以下是 C 语言的递归与迭代两种实现方式。

方法 1：递归实现快速幂

#include <stdio.h>// 递归实现快速幂算法
double myPow(double x, int n) {if (n == 0) return 1.0;  // 任何数的 0 次幂为 1if (n < 0) {// 处理负指数if (n == -2147483648) {  // 避免 n == -n 这种情况return 1.0 / (myPow(x, 2147483647) * x);}return 1.0 / myPow(x, -n);}// 快速幂递归double half = myPow(x, n / 2);if (n % 2 == 0) {return half * half;} else {return half * half * x;}
}int main() {double x = 2.0;int n = 10;printf("%f\n", myPow(x, n));  // 输出 1024.000000x = 2.1;n = 3;printf("%f\n", myPow(x, n));  // 输出 9.261000x = 2.0;n = -2;printf("%f\n", myPow(x, n));  // 输出 0.250000return 0;
}

方法 2：迭代实现快速幂（推荐）

迭代方法避免了递归调用的栈开销，采用位运算判断 n 的奇偶性并逐步累积结果：

#include <stdio.h>double myPow(double x, int n) {long long N = n;  // 使用 long long 避免溢出if (N < 0) {x = 1 / x;N = -N;}double result = 1.0;while (N > 0) {if (N % 2 == 1) {result *= x;  // 如果 N 是奇数，额外乘一次 x}x *= x;           // 平方底数N /= 2;           // 将 N 减半}return result;
}int main() {double x = 2.0;int n = 10;printf("%f\n", myPow(x, n));  // 输出 1024.000000x = 2.1;n = 3;printf("%f\n", myPow(x, n));  // 输出 9.261000x = 2.0;n = -2;printf("%f\n", myPow(x, n));  // 输出 0.250000return 0;
}

逐步解释

负指数处理：将负指数转化为正指数，并取倒数处理。如果 n 为负，将 x 替换为 1/x 并将 N 转为正数。
迭代循环：
- 通过循环对 N 进行二进制处理：如果 N 是奇数，将结果乘以当前的 x 值；如果 N 是偶数，直接进行 x 的平方处理，并让 N 右移。
返回结果：最终返回累积结果 result。