算法题每日一练—第62天：Pow(x, n)

Offer 驾到，掘友接招！我正在参与2022春招打卡活动，点击查看活动详情。

一、前言

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

题目链接：Pow(x, n)。

二、题目要求

样例 1

输入： x = 2.00000, n = 10
输出： 1024.00000
复制代码

样例 2

输入： x = 2.10000, n = 3
输出： 9.26100
复制代码

考察

1.位运算中等题型、快速幂
2.建议用时15~30min
复制代码

三、问题分析

本题是位运算的第17题，没了解过位运算相关知识点可以看这一篇文章，讲解比较详细：

算法题每日一练—第45天：位运算。

如果你了解过位运算相关知识点，但没有了解过快速幂，可以先看这一篇

知识点介绍，然后再回来做这一题会发现非常简单。

这一题其实套用位运算的模板就行了，最主要的是n的范围 -23^1 <= n <= 2^31-1，这不正好是int整形存储二进制的范围吗？

这里要注意一点，因为n有可能小于0，对于这种情况我们还是按照正数判断，最后取倒数就行了。

最后提交测试的时候，发现了几个恶心的测试用例怎么也过不了

最后我修改了题目给定的n，从int 改成long然后就莫名其妙的过了。

四、编码实现

class Solution {
public:
    double myPow(double x, long n) {
        int flag=1;//判断n负数的标记
        double base=x,ans=1;//初始化
        if(n<0)
        {
            flag=0;
            n=abs(n);//取正数
        }
        while(n)//快速幂模板
        {
            if(n&1)
                ans=ans*base;
            base*=base;
            n=n>>1;
        }
        if(flag)//正数输出结果
            return ans;
        else//取倒数输出
            return 1.0*1/ans;
    }
};
复制代码

五、测试结果

六、总结与提高

这一题是位运算分支的第17题，是快速幂的第2题。快速幂掌握其实不难，在网上找了半天，发现2个典型的快速幂运算，这两题做完快速幂也能基本掌握了。