# 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）

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

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

## 二、 快速幂

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

```swift
var res = 1
for _ in 0..<n {
    res *= x
}
return res
```

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

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

### 2.1 思路一：递归

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

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

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

#### Swift实现

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

```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 为例进行推导。

&#x20;x14(10) = x1110(2) = x1000(2) \* x100(2) \* x10(2)

换个方向，更直观：

&#x20;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            |
| :----: | :--: | :-----------------------: |
| 111`0` |   0  |           x0(2)           |
| 11`1`0 |  10  |           x10(2)          |
| 1`1`10 |  100 |     x10(2) \* x100(2)     |
| `1`110 | 1000 | x10(2) *x100(2)* x1000(2) |

#### Swift实现

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

```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 递归

```swift
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](/files/-MhGyEbWoasl2cbyaXRy)

### 3.2 非递归

```swift
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](/files/-MhGyEbYvh5HE-5ky34o)


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://ryukiedev.gitbook.io/wiki/shu-ju-jie-gou-yu-suan-fa/jian-zhi-offerswift/16.-shu-zhi-de-zheng-shu-ci-fang.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.