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)
}
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
}