面試 5：手寫 Java 的 pow() 實作

我們在處理一道程式設計面試題的時候，通常除了注意代碼規範以外，千萬要記得自己心中模拟一個單元測試。主要通過三方面來處理。

• 功能性測試
• 邊界值測試
• 負面性測試

不管如何，一定要保證自己代碼考慮的全面，而不要簡單地猜想使用者的輸入一定是正确的，隻是去實作功能。通常你編寫一個能接受住考驗的代碼，會讓面試官對你刮目相看，你可以不厲害，但已經充分說明了你的靠譜。

今天我們的面試題目是：

面試題：嘗試實作 Java 的 Math.pow(double base,int exponent) 函數算法，計算 base 的 exponent 次方，不得使用庫函數，同時不需要考慮大數問題。

面試題來源于《劍指 Offer》第 11 題，數字的整數次方。

不要介意 Java 真正的方法是 Math.pow(double var1,double var2)。

由于不需要考慮大數問題，不少小夥伴心中暗自竊喜，這題目也太簡單了，給我撞上了，運氣真好，于是直接寫出下面的代碼：

public class Test11 {

    private static double power(double base, int exponent) {
        double result = 1.0;
        for (int i = 0; i < exponent; i++) {
            result *= base;
        }
        return result;
    }

    public static void main(String[] args) {
        System.out.println(power(2, 2));
        System.out.println(power(2, 4));
        System.out.println(power(3, 1));
        System.out.println(power(3, 0));
    }
}
           

寫的快自然是好事，如果正确的話會被面試官認為是思維靈活。但如果考慮不周的話，恐怕就極容易被面試官認為是不靠譜的人了。在技術能力和靠譜度之間，大多數面試官更青睐于靠譜度。

我們上面确實做到了功能測試，但面試官可能會直接提示我們，假設我們的

exponent

輸入一個負值，能得到正确值麼？

跟着自己的代碼走一遍，終于意識到了這個問題，當

exponent

為負數的時候，循環根本就進不去，無論輸入的負數是什麼，都會傳回 1.0，這顯然是不正确的算法。

我們在數學中學過，給一個數值上負數次方，相當于給這個數值上整數次方再求倒數。

意識到這點，我們修正一下代碼。

public class Test11 {

    private static double power(double base, int exponent) {
        // 因為除了 0 以外，任何數值的 0 次方都為 1，是以我們預設為 1.0；
        // 0 的 0 次方，在數學書是沒有意義的，為了貼切，我們也預設為 1.0
        double result = 1.0;
        // 處理負數次方情況
        boolean isNegetive = false;
        if (exponent < 0) {
            isNegetive = true;
            exponent = -exponent;
        }
        for (int i = 0; i < exponent; i++) {
            result *= base;
        }
        if (isNegetive)
            return 1 / result;
        return result;
    }

    public static void main(String[] args) {
        System.out.println(power(2, 2));
        System.out.println(power(2, 4));
        System.out.println(power(3, 1));
        System.out.println(power(3, -1));
    }
}
           

我們在代碼中增加了一個判斷是否為負數的

isNegetive

變量，當為負數的時候，我們就置為 true，并計算它的絕對值次幂，最後傳回結果的時候傳回它的倒數。

面試官看到這樣的代碼，可能就有點按捺不住内心的怒火了，不過由于你此前一直面試回答的較好，也打算再給你點機會，面試官提示你，當

base

傳入 0，

exponent

傳入負數，會怎樣？

瞬間發現了自己的問題，這不是犯了數學最常見的問題，給 0 求倒數麼？

雖然 Java 的 Math.pow() 方法也存在這個問題，但我們這裡忽略不計。

于是馬上更新代碼。

public class Test11 {


    private static double power(double base, int exponent) {
        // 因為除了 0 以外，任何數值的 0 次方都為 1，是以我們預設為 1.0；
        // 0 的 0 次方，在數學書是沒有意義的，為了貼切，我們也預設為 1.0
        double result = 1.0;
        // 處理底數為 0 的情況，底數為 0 其他任意次方結果都應該是 0
        if (base == 0)
            return 0.0;
        // 處理負數次方情況
        boolean isNegetive = false;
        if (exponent < 0) {
            isNegetive = true;
            exponent = -exponent;
        }
        for (int i = 0; i < exponent; i++) {
            result *= base;
        }
        if (isNegetive)
            return 1 / result;
        return result;
    }

    public static void main(String[] args) {
        System.out.println(power(2, 2));
        System.out.println(power(2, 4));
        System.out.println(power(3, 1));
        System.out.println(power(0, -1));
    }
}
           

有了上一次的經驗，這次并不敢直接上交代碼了，而是認真檢查邊界值和各種情況。檢查 1 遍，2 遍，均沒有發現問題，送出代碼。

計算機表示小數均有誤差，這個在 Python 中尤其嚴重，但經數次測試，《劍指 Offer》中講的雙精度誤差問題似乎在 Java 的 == 運算符中并不存在。如有問題，歡迎指正。

上面的代碼基本還算整，健壯性也還不錯，但面試官可能還想問問有沒有更加優秀的算法。

仔細檢視，确實似乎是有辦法優化的，比如我們要求

power(2,16)

的值，我們隻需要先求出 2 的 8 次方，再平方就可以了；以此類推，我們計算 2 的 8 次方的時候，可以先計算 2 的 4 次方，然後再做平方運算.....妙哉妙哉！

需要注意的是，如果我們的幂數為奇數的話，我們需要在最後再乘一次我們的底數。

我們嘗試修改代碼如下：

public class Test11 {
    private static double power(double base, int exponent) {
        // 因為除了 0 以外，任何數值的 0 次方都為 1，是以我們預設為 1.0；
        // 0 的 0 次方，在數學書是沒有意義的，為了貼切，我們也預設為 1.0
        double result = 1.0;
        // 處理底數為 0 的情況，底數為 0 其他任意次方結果都應該是 0
        if (base == 0)
            return 0.0;
        // 處理負數次方情況
        boolean isNegetive = false;
        if (exponent < 0) {
            isNegetive = true;
            exponent = -exponent;
        }
        result = getTheResult(base, exponent);
        if (isNegetive)
            return 1 / result;
        return result;
    }

    private static double getTheResult(double base, int exponent) {
        // 如果指數為0，傳回1
        if (exponent == 0) {
            return 1;
        }
        // 指數為1，傳回底數
        if (exponent == 1) {
            return base;
        }
        // 遞歸求一半的值
        double result = getTheResult(base, exponent >> 1);
        // 求最終值，如果是奇數，還要乘一次底數
        result *= result;
        if ((exponent & 0x1) == 1) {
            result *= base;
        }
        return result;

    }

    public static void main(String[] args) {
        System.out.println(power(2, 2));
        System.out.println(power(2, 4));
        System.out.println(power(3, -1));
        System.out.println(power(0.1, 2));
    }
}
           

完美解決。

在送出代碼的時候，還可以主動提示面試官，我們在上面用右移運算符代替了除以 2，用位與運算符代替了求餘運算符 % 來判斷是一個奇數還是一個偶數。讓他知道我們對程式設計的細節真的很重視，這大概也就是細節決定成敗吧。一兩個細節的打動說不定就讓面試官下定決心給我們發放 Offer 了。

位運算的效率比乘除法及求餘運算的效率要高的多。

因為移位指令占 2 個機器周期，而乘除法指令占 4 個機器周期。從硬體上看，移位對硬體更容易實作，是以我們更優先用移位。

好了，今天我們的面試精講就到這裡，我們明天再見！