文章目录加载中

数值的整次方

# 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));
本文来自心谭博客:xin-tan.com,经常更新web和算法的文章笔记,前往github查看目录归纳:github.com/dongyuanxin/blog