[劍指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;
}