数值的整次方

# 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));

# 优化思路

在 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));