Skip to main content

数值的整数次方

  • 题源：《剑指 Offer: 面试题 16》P110
  • 在线：LeetCode: 50

题目​

实现 pow(x, n) ，即计算 x 的 n 次幂函数。不得使用库函数，同时不需要考虑大数问题。

示例 1:

输入: 2.00000, 10
输出: 1024.00000

示例  2:

输入: 2.10000, 3
输出: 9.26100

示例  3:

输入: 2.00000, -2
输出: 0.25000
解释: 2-2 = 1/22 = 1/4 = 0.25

说明:

  • -100.0 < x < 100.0
  • n  是 32 位有符号整数，其数值范围是  [−2**31, 2**31 − 1] 。

思路​

  1. 如果直接用循环乘的话，对于 n 为正数没有问题，n 为 0 的话要返回 1
  2. 如果 n 为负数的话，需要取倒数，这个地方也可利用递归去做
  3. 利用递归将时间复杂度降低到 O(logn) 级别

图：a 的 n 次方的递推公式

代码实现​

/**
 * @param {number} x
 * @param {number} n
 * @return {number}
 */
function myPow(x, n) {
  if (n === 0) return 1;
  if (n < 0) return 1 / myPow(x, -n);
  if (n & 1) return myPow(x * x, n >>> 1) * x;
  return myPow(x * x, n >>> 1);
}

关于 JS 位运算注意事项:

  • 首先要明确一点，位移操作是针对二进制而言，在二进制中都是对的规则，只不过转成十进制后让人感觉结果不太对，要想利用位移达到操作十进制数据的目的得熟知一些小技巧。
  • >> 是有符号右移，高位补符号位，尤其注意 2**31 这个正数，高位会补 1，导致其变成负数 -1073741824，故负数右移肯定是负数，但正数右移不一定是正数。
  • >>> 是无符号右移，高位始终补 0，2**31>>>1结果是 1073741824，无论是正数还是负数，右移的结果都是正数。
  • -3>>>0 会将最高位的 1 当成是值而不是符号，故其结果是 4294967293, 尤其注意的是这并不能转成绝对值。
  • JS 的位运算只支持 32 位有符号整数，超过将会截断，即 2**31: [-2147483648, 2147483648]，无论是使用 >> 还是 >>> 有效位运算最大正数都只支持到 2**31，即 2147483648, 故 4294967296 >>> 1 为 0。那为什么 -2147483648>>1 也会得到正确的结果，其实在二进制的世界中，已经发生了截断，实际上进行的是 ``
  • << 不一定就是安全的，因为 JS 默认的是 32 位有符号整数，196<<24, 刚好将 1 移动到最高位被当初了符号为，故为 -1006632960, 要想得到正确的十进制结果得 (196<<24)>>>0。
  • 不能直接写成 1<<32, 1>>32, 他们的结果都是 1, 要写成 1>>31>>1, 1<<31<<1, 或者用循环逐次移动 1 位，这样结果才会是 0。
  • 优先级高低： - ** >> >>> === &, 判断奇偶时候不能写成 n & 1 === 1 , 要么左边加 (), 要么不要写 === 1。
  • -23**2 会语法报错，因为在语法分析的时候运算符优先级会有歧义，(-23)**2 还是 -(23**2)，要加上括号明确意图。
Uncaught SyntaxError: Unary operator used immediately before exponentiation expression. Parenthesis must be used to disambiguate operator precedence

复杂度​

  • 时间复杂度：O(logn)，对每一个 n 的二进制位表示，我们都至多需要累乘 1 次。
  • 空间复杂度：O(logn)，使用了递归函数，也并非尾递归。

拓展​

如果想让空间复杂度要降到 O(1)，该如何实现呢？