pow-x-n

题目

实现 pow(x, n), 即计算 x 的 n 次幂函数.

提示:

• -100.0 < x < 100.0
• -2³¹ <= n <= 2³¹-1
• n 是一个整数
• -10⁴ <= xⁿ <= 10⁴

示例

输入: `x = 2.00000`, `n = 10`

输出: `1024.00000`

输入: `x = 2.00000`, `n = -2`

输出: `0.25000`

题解

JavaScript - 快速幂算法

快速幂算法的本质是分治算法, 比如求 x⁶⁴, 每次直接把上一次的结果进行平方, 计算 66 次就可以得到 x⁶⁴ 的值,而不需要对 x 乘 63 次.

即: x -> x² -> x⁴ -> x⁸ -> x¹⁶ -> x³² -> x⁶⁴

再看下面这个例子, 我们直接把上一次的结果进行平方, x⁴ -> x⁹, x⁹ -> x¹⁹, x¹⁹ -> x³⁸, x³⁸ -> x⁷⁷ 这些步骤中, 我们把上一次的结果进行平方后, 还要额外乘一个 x.

即: x -> x² -> x⁴ -> x⁹ -> x¹⁹ -> x³⁸ -> x⁷⁷

从前往后看比较费劲, 从后往前看就有分治的思想了:

1. 计算 xⁿ, 可以先递归的计算出 y = x^{n / 2}
2. 根据递归计算的结果, 如果 n 是偶数, 那么 xⁿ = y²; 否则 xⁿ = y² * x
3. 递归的边界为 n = 0, 任意数的 0 次方均为 1

/**
 * @param {number} x
 * @param {number} n
 * @return {number}
 */
var myPow = function (x, n) {
  if (x === 1 || n === 0) return 1
  if (n < 0) return 1 / helper(x, Math.abs(n))
  if (n > 0) return helper(x, n)
}

var helper = function (x, n) {
  if (n === 0) return 1

  if (n % 2 === 1) {
    const half = helper(x, (n - (n % 2)) / 2)
    return x * half * half
  } else {
    const half = helper(x, n / 2)
    return half * half
  }
}

JavaScript - 位运算

/**
 * @param {number} x
 * @param {number} n
 * @return {number}
 */
var myPow = function (x, n) {
  // 考虑负数情况, 即变为倒数
  if (n < 0) {
    x = 1 / x
    n = -n
  }

  let res = 1

  while (n) {
    //判断 n 的二进制最后一位是否是 1, 如果是 1 则将结果乘以 x
    if (n & 1) res *= x

    x *= x

    // 进行无符号右移 1 位, 相当于此处不能使用有符号右移 >>
    // 因为当 n 为 -2^31 转换成正数时的二进制位 10000000000000000000000000000000
    // 如果采用有符号右移时会取最左侧的数当符号即 1, 导致返回的结果是 -1073741824
    n >>>= 1
  }

  return res
}

Rust

pub fn my_pow(x: f64, n: i32) -> f64 {
    let mut x = x;
    let mut n = n as i64;
    let mut res = 1.0;

    if n < 0 {
        x = 1.0 / x;
        n = -n;
    }

    while n != 0 {
        if n & 1 == 1 {
            res *= x;
        }

        x *= x;
        n >>= 1;
    }

    res
}