LeetCode_50_Pow(x,n)

题目链接

• https://leetcode.cn/problems/powx-n/

题目描述

实现 pow(x, n) ，即计算 x 的整数 n 次幂函数（即，x^n ）。

示例 1：

输入：x = 2.00000, n = 10
输出：1024.00000
1
2

示例 2：

输入：x = 2.10000, n = 3
输出：9.26100
1
2

示例 3：

输入：x = 2.00000, n = -2
输出：0.25000
解释：2-2 = 1/22 = 1/4 = 0.25
1
2
3

提示：

• -100.0 < x < 100.0
• $-2^{31}<=n<=2^{31}-1$
• $-10^4<=x^n<=10^4$

解题思路

快速幂+二分法

• $x^n=x^{n/2}\ast x^{n/2}=(x^2{)}^{n/2}$,令n/2为整数，则需要分奇偶两种情况，即
  x n = { ( x 2 ) n / 2 , n 为偶数 x ( x 2 ) n / 2 , n 为奇数 x^n =

  {(x2)n/2,n为偶数x(x2)n/2,n为奇数" role="presentation" style="position: relative;">{(x2)n/2,x(x2)n/2,n为偶数n为奇数$$\{\begin{array}{ll}(x^2{)}^{n/2},& n\text{为偶数}\\ x(x^2{)}^{n/2},& n\text{为奇数}\end{array}$$
  xn={(x2)n/2,x(x2)n/2,​n为偶数n为奇数​

• 幂结果获取：

  • 根据推导，可通过循环$x=x^2$操作，每次把幂从n降至n/2，直到将幂降为0
  • 设ans = 1,则初始状态为$x^n=x^n\ast ans$.在循环二分时，每当n为奇数时，将多出的一项x乘入ans中，则最终可以转化为$x^n=x^0\ast ans=ans$
  • 

• 转化为位运算

  • 向下整除n/2等价于右移一位n >> 1
  • 取余数n % 2等价于判断二进制的最右位n & 1

AC代码

class Solution {
    public double myPow(double x, int n) {
        if (x == 0.0) {
            return 0.0;
        }
        long b = n;
        double ans = 1.0;
        if (b < 0) {
            x = 1 / x;
            b = -b;
        }
        while (b > 0) {
            if ((b & 1) == 1) {
                ans *= x;
            }
            x *= x;
            b >>= 1;
        }
        return ans;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21