题目描述

实现函数 double Power(double base, int exponent)，求base的exponent次方。
注意： 1.保证base和exponent不同时为0。
2.不得使用库函数，同时不需要考虑大数问题。
3.有特殊判题，不用考虑小数点后面0的位数。

题解：来自官方题解牛客题霸

假设求x^6 ,已知6可以表示成二进制110，

代码

class Solution {
public:

    double Power(double b, int n) {
        if (n < 0) {
            b = 1 / b;
            n = -n;
        }
        double x = b; // 记录x^0, x^1, x^2 ...
        double ret = 1.0;
        while (n) {
            if (n&1) {
                ret *= x; // 二进制位数是1的，乘进答案。
            }
            x *= x;
            n >>= 1;
        }
        return ret;
    }
};

题解2：递归

代码

class Solution {
public:
    //递归函数
    double d_power(double base, int exponent){
        //递归出口
        if(exponent == 1)
            return base;
        double result = d_power(base,exponent>>1);
            if(exponent&1){
                return result*result*base;
            }
            else
                return result*result;
        return base;
    }
    double Power(double base, int exponent) {
        if(0== base)
            return 0;
        if(0 == exponent)
            return 1;
        if(exponent<0){
            base = 1/base;
            exponent=-exponent;
        }
        //递归
        return d_power(base, exponent);
        
    }
};