剑指offer 面试题16 数值的整数次方

wenkun97

于 2019-11-02 15:32:50 发布

阅读量120

点赞数

分类专栏：剑指offer 文章标签：剑指offer

本文链接：https://blog.csdn.net/hello_my_coder/article/details/102872499

版权

剑指offer 专栏收录该内容

53 篇文章

订阅专栏

本文深入解析了快速幂算法，一种高效计算浮点数次方的方法，通过递归将复杂度降至O(logn)，并提供了C++实现代码示例，包括处理正、负指数的情况。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

题目描述
给定一个double类型的浮点数base和int类型的整数exponent。求base的exponent次方。

保证base和exponent不同时为0

注意考虑exp为负数和零的情况，另外，求次方的时候，利用公式，
aⁿ={a^n/2*a^n/2 -------n 为偶数
a^(n-1)/2*a^(n-1)/2*a--------n为奇数}

降为O(logn)的复杂度
此外，可以用右移运算代替除以2，用&0x01代替%2

#include <iostream>
#include <string>
#include <memory>
#include <vector>
#include<cmath>
#include<algorithm>
using namespace std;

class Solution {
public:
    double powerWithPos(double base,int exp) {
        if(exp==0) {
            return 1;
        } else if(exp==1) {
            return base;
        }
        double res=powerWithPos(base,exp>>1);
        res*=res;
        if(exp&0x01) {
            res*=base;
        }
        return res;
    }
    double Power(double base,int exponent) {                                                                                                                                                                                                                                                                                                                                                                                                                                    
        int neg=0;
        if(exponent<0) {
            exponent=-exponent;
            neg=1;
        }
        double res=powerWithPos(base,exponent);
        if(neg==1) {
            res=1/res;
        }
        return res;
    }
    
};

int main()
{
    Solution sol;
    int n;
    // cin>>n;
    double res=sol.Power(2,-3);
    cout<<res<<endl;
    system("pause");
    return 0;
}