幂运算 pow(x, n) 的一个迭代实现

求一个浮点数的整数次幂： https://leetcode.com/problems/powx-n/

Implement pow(x, n), which calculates x raised to the power n (i.e. xⁿ).

 

Example 1:

Input: x = 2.00000, n = 10
Output: 1024.00000

Example 2:

Input: x = 2.10000, n = 3
Output: 9.26100

Example 3:

Input: x = 2.00000, n = -2
Output: 0.25000
Explanation: 2-2 = 1/22 = 1/4 = 0.25

 

Constraints:

• -100.0 < x < 100.0
• -231 <= n <= 231-1
• -104 <= xn <= 104

基本就是分治思想，用递归就能很方便地实现，也可以把递归改写成迭代，但我在 Discuss 区看见了一个精奇的迭代思路¹。

例如，现求 $x^9$，把指数写成二进制形式，并按照每个二进制位拆分为累乘：

$$x^9 = x^{1001_2} = x^{1000_2} x^{000_2} x^{00_2} x^{1_2}$$

观察可以发现，当对应的二进制位为 0 时，该项值为 1，可以忽略；当对应的二进制位为 1 时，该项保留，其值为 $x^1, x^2, x^4, x^8, …$

迭代思路：从低到高依次取指数的二进制位，如果该位为 1，结果累乘，否则忽略。

C 语言实现如下：

double myPow_50_1(double x, int n) {
    if (n == 0) return 1;

    double ret = 1;
    for (unsigned e = n < 0 ? 0u - n : n; e > 0; e >>= 1) {
        if (e & 1)
            ret = ret * x;
        x *= x;
    }
    return n >= 0 ? ret : 1 / ret;
}

注意指数为负数的情况，求绝对值用 0u - n 先转换为无符号整数，否则当指数为 INT_MIN 时 LeetCode 编译器会报错。

实现源码

https://github.com/qianbinbin/leetcode

参考资料