[LC]16. 数值的整数次方

🚩传送门：力扣题目

题目

实现 ，即计算 的 次幂函数（即，）。不得使用库函数，同时不需要考虑大数问题。

示例 1：

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

示例 2：

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

示例 3：

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

解题思路：二进制

正常我们求解 我们会将自己相乘 次，速度太慢

我们不难到发现 、、
对于 ，相比于将自己相乘 次，使用二进制自乘，只需要次，越大效果越好，当前 是否相乘取决于二进制当前位是还是

算法流程：

1. 当 时：直接返回 （避免后续 操作报错）。
2. 初始化 ；
3. 当 时：把问题转化至 的范围内，即执行 ， ；

4. 循环计算：当 时跳出；

   • 当 时：将当前 乘入 （即 ）；
   • 执行 （）
   • 执行 右移一位（即 ）。

5. 返回 。

复杂度分析

时间复杂度：，二分的时间复杂度为对数级别。

空间复杂度：，占用常数大小额外空间。

官方代码

class Solution {
    public double myPow(double x, int n) {
        // 指数
        long ex=n;
        double res = 1;
        if(n<0){
            ex=-ex;
            x=1/x;
        }
        while (ex != 0) {
            if ((ex & 1) == 1) {
                res = res * x;
            }
            ex = ex >> 1;
            x = x * x;
        }
        return res;
    }
}