剑指 Offer 16. 数值的整数次方

题目描述

实现 pow(x, n) ，即计算 x 的 n 次幂函数（即，xⁿ）。不得使用库函数，同时不需要考虑大数问题。

示例 1：

输入：x = 2.00000, n = 10
输出：1024.00000

示例 2：

输入：x = 2.10000, n = 3
输出：9.26100

示例 3：

输入：x = 2.00000, n = -2
输出：0.25000
解释：2^-2 = 1/2² = 1/4 = 0.25

提示：

-100.0 < x < 100.0
-2³¹ <= n <= 2³¹-1
-10⁴ <= xⁿ <= 10⁴

注意：本题与主站 50 题相同：https://leetcode-cn.com/problems/powx-n/

解法一：递归

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19


func myPow(x float64, n int) float64 {
    var recur func(x float64, n int) float64
    recur = func(x float64, n int) float64 {
        if 0 == n {
            return 1
        }
        t := recur(x, n/2)
        if n&1 == 0 {
            return t * t
        } else {
            return t * t * x
        }
    }
    if n < 0 {
        return 1 / recur(x, -n)
    } else {
        return recur(x, n)
    }
}

解法二：迭代

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17


func myPow(x float64, n int) float64 {
    contributor := x
    ans := 1.0
    a := n ^ (n >> 31) - (n >> 31)
    for a > 0 {
        if a&1 == 1 {
            ans *= contributor
        }
        a >>= 1
        contributor *= contributor
    }
    if n < 0 {
        return 1 / ans
    } else {
        return ans
    }
}

总结

使用位运算取一个 32 位整数 a 的绝对值：abs(a) = a ^ (a » 31) - (a » 31)，其中 ^ 表示异或运算。