【劍指Offer】數值的整數次方

• 2020 年 4 月 22 日
• 筆記
• 劍指Offer, 整數快速冪

題目描述

給定一個double類型的浮點數base和int類型的整數exponent。求base的exponent次方。
保證base和exponent不同時為0

解法1

最直接的思路，計算base的exponent次方，則將base連乘exponent次即可，時間複雜度為O(exponent)
但是要注意處理特殊情況：

• 如果底數base等於0則直接返回0
• 非0數的0次方等於1
• 當指數為負數時的結果，相當於用1除以指數為正數時的結果

還有一個坑需要注意，下面的程式碼中使用了long y = exponent;，需要將exponent轉換為long類型
是因為exponent可以等於-2147483648（int類型的最小值），如果直接進行-exponent操作，由於int類型的最大值是2147483647，則會導致越界，出現錯誤的結果

實現程式碼

public double Power(double thebase, int exponent)
{
    if(thebase == 0) return 0;
    long y = exponent;  // 避免越界
    if(y < 0){
        thebase = 1 / thebase;
        y = -y;
    } 
    double ret = 1;
    for(double i = 0; i < y; i ++){
        ret *= thebase;
    }
    return ret;
}

解法2

可以根據二分的思路，利用遞歸每次求指數的一半的次方結果，然後再將遞歸的結果相乘得到完整的指數次方
由於求指數的一半，即整數除以2的結果會自動向下取整，所以需要特殊處理指數為奇數時的情況，當指數為奇數時，需要在遞歸結果相乘的基礎上再乘以一次底數
程式碼中使用的位運算e >> 1相當於e / 2來計算指數的一半
程式碼中通過位運算(e & 1) == 1 來判斷指數是奇數還是偶數（奇數的二進位表示最低位一定是1，偶數的二進位表示最低位一定是0），相當於(e % 2) == 1
使用位運算會有更快的執行效率

實現程式碼

public double Power2(double thebase, int exponent)
{
    if(thebase == 0) return 0;
    if(exponent == 0) return 1;
    long e = exponent;  // 避免越界
    if(exponent < 0){
        e = - e;
        thebase = 1 / thebase;
    }
    if(e == 1) return thebase;
    double ret = Power2(thebase, (int)(e >> 1));
    return (e & 1) == 1 ? thebase * ret * ret : ret * ret;
}

解法3

求解整數m的n次方，一般是mⁿ = m * m * m …..，連乘n次，演算法複雜度是O(n)，這樣的演算法效率太低，我們可以通過減少相乘的次數來提高演算法效率，即快速冪
對於n我們可以用二進位表示，以14為例，14 = 1110

可以發現這樣的規律，指數n的二進位從低位到高位依次對應底數m的1次方，2次方，4次方，8次方…，當該二進位位是1的時候，則乘以底數對應的次方數，如果該二進位位是0，則不能乘以底數對應的次方數，即乘以1。
例如，m⁸對應的二進位位是1，所以最終結果中有m⁸
m¹對應的二進位位是0，所以最終結果中只有m⁰，即1
使用快速冪後，原本需要的14次連乘，現在只需要4次連乘。
那麼怎樣得到一個整數的二進位位呢，又怎樣判斷該二進位位是0還是1呢
可以使用與運算和右移運算，例如對於14 = 1110

• 和1按位與得到0，即第一個二進位位是0
• 1110右移一位，得到0111，和1按位與得到1，即第二個二進位位是1
• 0111右移一位，得到0011，和1按位與得到1，即第三個二進位位是1
• 0011右移一位，得到0001，和1按位與得到1，即第四個二進位位是1
• 0001右移一位，得到0000，等於0則，演算法結束

實現程式碼

public double Power3(double thebase, int exponent)
{
    if(thebase == 0) return 0;
    long y = exponent;  // 避免越界
    if(y < 0){
        thebase = 1 / thebase;
        y = -y;
    } 
    double ret = 1;
    while(y > 0){
        if((y & 1) == 1){
            ret *= thebase;
        }
        thebase *= thebase;
        y >>= 1;
    }
    return ret;
}

更多演算法題目的完整描述，AC程式碼，以及解題思路可以查看GitHub倉庫Algorithm