Links

16.数值的整数次方

一、 题目

实现 pow(x, n) ,即计算 x 的 n 次幂函数(即,xn)。不得使用库函数,同时不需要考虑大数问题。
示例 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^(2)) = 1/4 = 0.25
提示:
-100.0 < x < 100.0
-231 <= n <= 231-1
-104 <= xn <= 104
来源:力扣(LeetCode)
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

二、 快速幂

幂运算是我们最常用的运算之一。如果我们要求 x 的 N 次幂,那么想当然的就会写出一个 N 次的循环,然后累乘得到结果。这种幂运算的复杂度是O(N)。
var res = 1
for _ in 0..<n {
res *= x
}
return res
那么有没有更快的运算方式呢?
在计算机领域有一种常用的快速幂算法:蒙哥马利幂(Montgomery reduction)算法。将复杂度从O(N) 降到了 O(logN)

2.1 思路一:递归

  • 若 N 为偶数,可以先求 xN/2,然后再平方。
  • 若 N 为奇数,可以先求 x(N-1)/2,然后再平方,再乘以x
快速幂的最基础思想就是上面两条了。
求解 xN/2,x(N-1)/2 时也可以用到上面的思路,每次将指数除以2,每次都可以将复杂度降低一半,知道最后指数为1。

Swift实现

  • 这里不考虑大数,仅作为思路展示
func quickpow(_ x: Int, _ n: Int) -> Int {
if n == 0 {// 直到最后指数为0
return 1
}
let res = quickpow(x, n/2)
if n%2 != 0 {// n 为奇数
return res * res * x
}
// n为偶数
return res * res
}

2.2 思路二:二进制拆分

我们以 x14 为例进行推导。
x14(10) = x1110(2) = x1000(2) * x100(2) * x10(2)
换个方向,更直观:
x1110(2) = x10(2) * x100(2) * x1000(2)
推论:
  • 设 x 的 N 次幂等于 res
    • 1: 在指数 N 的二进制形式下,从最低位开始左移一位,x自乘一次(和指数N左移一位保持一致)
    • 如果当前位为1
      • 当前位a到最低位,中间位全部置0时表示的值b,xb的累乘
    • 如果当前位位0
      • 执行1
    • 循环直到指数N等于0
当前位
指数b
res
1110
0
x0(2)
1110
10
x10(2)
1110
100
x10(2) * x100(2)
1110
1000
x10(2) x100(2) x1000(2)

Swift实现

  • 这里不考虑大数,仅作为思路展示
func quickpow(_ x: Int, _ n: Int) -> Int {
var res = 1
var x = x
var n = n
while n > 0 {
if n & 1 == 1 { // 如果n的当前末位为1
res *= x // res乘上当前的x
}
x *= x// x自乘,当前指数左移一位
n >>= 1// n右移一位,想当于 n / 2
}
return res
}

三、 解题

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

3.1 递归

func myPow(_ x: Double, _ n: Int) -> Double {
// 特殊处理 0 1 -1 可以直接 return 结果
if x == 0 || x == 1 {
return x
}
else if x == -1 {
return (n & 1 == 1 ? -1 : 1)
}
if n == 0 {
return 1
}
else if n < 0 {
return myPow(1/x, -n)
}
else if n == 1 {
return x
}
let temp = myPow(x, n >> 1)
return temp * temp * ((n & 1 == 1) ? x : 1)
}
1

3.2 非递归

func myPow(_ x: Double, _ n: Int) -> Double {
// 特殊处理 0 1 -1 可以直接 return 结果
if x == 0 || x == 1 {
return x
}
else if x == -1 {
return (n & 1 == 1 ? -1 : 1)
}
if n == 0 {
return 1
}
var ans: Double = 1
var power = abs(n)
var newX = x
while power > 0 {
if power & 1 == 1 {
ans *= newX
}
newX *= newX
power = power >> 1
}
return n < 0 ? 1 / ans : ans
}
2