1. 题目描述

题目：实现函数 double Power（double base, intexponent），求 base 的 exponent 次方。不得使用库函数，同时不需要考虑大数问题

2. 思路分析

简单思路：最简单的做法是循环，但是要考虑异常值的检验。比如指数是负数，底数为 0。

优化思路：书上提供了一种复杂度为 $O(logN)$ 的做法。比如我们要求 32 次方，那么只要求出 16 次方再平方即可。依次类推，是递归函数的结构。

递推公式如下：

$$
a^n=\left{
\begin{aligned}
a^{n/2}*a^{n/2} ; n为偶数\
a^{(n - 1)/2}*a^{(n - 1)/2} ; n为奇数
\end{aligned}
\right.
$$

需要注意的是，如果幂是奇数，例如 5 次方，可以先计算 2 次方，结果平方后（4 次方），再乘以自身（5 次方）。按照此思路处理。

3. 代码实现

简单思路

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
/**
 *
 * @param {Number} base
 * @param {Number} exp
 */
function pow(base, exp) {
    // 规定0的任何次方均为0
    if (!base) {
        return 0
    }
    let result = 1,
        absExp = Math.abs(exp)

    for (let i = 0; i < absExp; ++i) {
        result *= base
    }

    // 对于指数小于0的情况，求其倒数
    if (exp < 0) {
        result = 1 / result
    }

    return result
}

/**
 * 以下是测试代码
 */

console.log(pow(2, -2))
console.log(pow(2, 2))
console.log(pow(2, 0))
console.log(pow(0, -9))

优化思路

在 Js 中整数除 2 不会自动取整，可以使用Math.floor()。但更好的做法是使用>>位运算。

判断奇数可以用%2判断。但更好的做法是和1进行&运算后（除了最后 1 位，都被置 0 了），判断是不是 1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
/**
 * 求base 的 exp次幂，其中exp永远是正数
 * @param {Number} base
 * @param {Number} exp
 */
function unsignedPow(base, exp) {
    if (exp === 0) {
        return 1
    } else if (exp === 1) {
        return base
    }

    let result = pow(base, exp >> 1)
    result *= result
    if (exp & (1 === 1)) {
        result *= base
    }

    return result
}

/**
 * 求 base的exp次幂
 * @param {Number} base
 * @param {Number} exp
 */
function pow(base, exp) {
    if (!base) {
        return 0
    }

    let absExp = Math.abs(exp)

    return exp < 0 ? 1 / unsignedPow(base, absExp) : unsignedPow(base, absExp)
}

/**
 * 以下是测试代码
 */

console.log(pow(2, 2))
console.log(pow(2, 0))
console.log(pow(0, -9))
console.log(pow(2, -2))