大师兄

1. 题目描述

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

2. 思路分析

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

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

递推公式如下：

为偶数为奇数

需要注意的是，如果幂是奇数，例如 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));
在 GitHub 上编辑此页2023/9/23 16:50:18