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. 代码实现

简单思路

/**
 *
 * @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));
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

优化思路

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

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

/**
 * 求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));
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