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

2018-08-24

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

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

 

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 区看见了一个精奇的迭代思路1

例如,现求 $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 语言实现如下:

leetcode/c/src/powx_n.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

参考资料


  1. Iterative Log(N) solution with Clear Explanation - LeetCode Discuss  ↩︎

LeetCode算法位操作
知识共享许可协议
本作品采用知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议进行许可。

CSAPP 计算机系统漫游

Linux 折腾手记