[剑指offer]数值的整数次方

题目描述

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

解题思路

1. 指数为负时，可以先对指数求绝对值，算出次方的结果后再取倒数
2. 当底数为0，指数为负时，会出现对0求倒数情况，要特殊处理
3. 0的0次方在数学上没有意义，因此无论输出0还是1都是可以接受的

4. 在计算次方的时候，除了简单的遍历，我们可以使用递归的思想，如下公式，来减少计算量：
   image

参考代码

public class Solution {
    public double Power(double base, int exponent) {
        int n = exponent;
        if(exponent==0){
            // 当指数为0底数为0时，没有意义，返回0或者返回1都可以
            return 1;
        }else if(exponent < 0){
            if(base == 0){
                throw new RuntimeException("分母不能为0"); 
            }
            n = -exponent;
        }
        double res = PowerUnsignedExponent(base, n);
        return exponent<0? 1/res: res;
  }
    public double PowerUnsignedExponent(double base, int n){
        if(n == 0)
            return 1;
        if(n == 1)
            return base;
        //递归
        double res = PowerUnsignedExponent(base, n/2);
        res *= res;
        if(n%2 == 1)
            res *= base;
        return res;
    }
}

代码优化

可以使用右移运算符代替除以2，用位与运算符代替求余运算符（%）来判断一个数是奇数还是偶数。

public double PowerUnsignedExponent(double base, int n){
        if(n == 0)
            return 1;
        if(n == 1)
            return base;
        //递归
        double res = PowerUnsignedExponent(base, n>>1);
        res *= res;
        if((n & 0x1) == 1)
            res *= base;
        return res;
}