数值的整数次方

961 字

5 分钟

数值的整数次方

2021-08-12

2026-10-12

数据结构与算法

「剑指Offer」Swift

一、题目#

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

示例 1：

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

示例 2：

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

示例 3：

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

提示：

1
-100.0 < x < 100.0
2
-231 <= n <= 231-1
3
-104 <= xn <= 104

来源：力扣（LeetCode）

链接：https://leetcode-cn.com/problems/shu-zhi-de-zheng-shu-ci-fang-lcof

著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

二、快速幂#

幂运算是我们最常用的运算之一。如果我们要求 x 的 N 次幂，那么想当然的就会写出一个 N 次的循环，然后累乘得到结果。这种幂运算的复杂度是O(N)。

1
var res = 1
2
for _ in 0..<n {
3
    res *= x
4
}
5
return res

那么有没有更快的运算方式呢？

在计算机领域有一种常用的快速幂算法：蒙哥马利幂（Montgomery reduction）算法。将复杂度从O(N) 降到了 O(logN)

2.1 思路一：递归#

若 N 为偶数，可以先求 x^N/2，然后再平方。
若 N 为奇数，可以先求 x^(N-1)/2，然后再平方，再乘以x

快速幂的最基础思想就是上面两条了。

求解 x^N/2，x^(N-1)/2 时也可以用到上面的思路，每次将指数除以2，每次都可以将复杂度降低一半，知道最后指数为1。

Swift实现#

这里不考虑大数，仅作为思路展示

1
func quickpow(_ x: Int, _ n: Int) -> Int {
2
    if n == 0 {// 直到最后指数为0
3
        return 1
4
    }
5
    let res = quickpow(x, n/2)
6
    if n%2 != 0 {// n 为奇数
7
        return res * res * x
8
    }
9
    // n为偶数
10
    return res * res
11
}

2.2 思路二：二进制拆分#

我们以 x¹⁴ 为例进行推导。

x^{14₍₁₀₎} = x^{1110₍₂₎} = x^{1000₍₂₎} * x^100₍₂₎ * x^10₍₂₎

换个方向，更直观：

x^{1110₍₂₎} = x^10₍₂₎ * x^100₍₂₎ * x^{1000₍₂₎}

推论：

设 x 的 N 次幂等于 res
- 1: 在指数 N 的二进制形式下，从最低位开始左移一位，x自乘一次（和指数N左移一位保持一致）
- 如果当前位为1
  - 当前位a到最低位，中间位全部置0时表示的值b，x^b的累乘
- 如果当前位位0
  - 执行1
- 循环直到指数N等于0

当前位	指数b	res
111`0`	0	x^0₍₂₎
11`1`0	10	x^10₍₂₎
1`1`10	100	x^10₍₂₎ * x^100₍₂₎
`1`110	1000	x^10₍₂₎ * x^100₍₂₎ * x^{1000₍₂₎}

Swift实现#

这里不考虑大数，仅作为思路展示

1
func quickpow(_ x: Int, _ n: Int) -> Int {
2
    var res = 1
3
    var x = x
4
    var n = n
5

6
    while n > 0 {
7
        if n & 1 == 1 { // 如果n的当前末位为1
8
            res *= x // res乘上当前的x
9
        }
10
        x *= x// x自乘，当前指数左移一位
11
        n >>= 1// n右移一位，想当于 n / 2
12
    }
13

14
    return res
15
}

三、解题#

本题的条件与上面介绍的快速幂中的例子略有不同，调整一下即可。

3.1 递归#

1
func myPow(_ x: Double, _ n: Int) -> Double {
2
    // 特殊处理 0 1 -1 可以直接 return 结果
3
    if x == 0 || x == 1 {
4
        return x
5
    }
6
    else if x == -1 {
7
        return (n & 1 == 1 ? -1 : 1)
8
    }
9

10
    if n == 0 {
11
        return 1
12
    }
13
    else if n < 0 {
14
        return myPow(1/x, -n)
15
    }
16
    else if n == 1 {
17
        return x
18
    }
19

20
    let temp = myPow(x, n >> 1)
21
    return temp * temp * ((n & 1 == 1) ? x : 1)
22
}

3.2 非递归#

1
func myPow(_ x: Double, _ n: Int) -> Double {
2
    // 特殊处理 0 1 -1 可以直接 return 结果
3
    if x == 0 || x == 1 {
4
        return x
5
    }
6
    else if x == -1 {
7
        return (n & 1 == 1 ? -1 : 1)
8
    }
9

10
    if n == 0 {
11
        return 1
12
    }
13

14
    var ans: Double = 1
15
    var power = abs(n)
16
    var newX = x
17
    while power > 0 {
18
        if power & 1 == 1 {
19
            ans *= newX
20
        }
21
        newX *= newX
22
        power = power >> 1
23
    }
24
    return n < 0 ? 1 / ans : ans
25
}