題目

實現(xiàn)函數(shù)double Power(double base, int exponent)，求base的exponent次方。不得使用庫函數(shù)，同時不需要考慮大數(shù)問題

思路1

由于不需要考慮大數(shù)問題，實現(xiàn)很簡單，如下

double Power(double base, int exponent)
{
    double result = 1.0;
    for (int i = 1; i <= exponent; i++) {
        result *= base;
    }
    return  result;
}

但是我們少考慮了一些情況，比如：如果輸入指數(shù)（exponent）是零和負數(shù)的時候怎么辦？如果底數(shù)（base）是零怎么辦？這些情況都沒有處理，上面的代碼只考慮了指數(shù)是正數(shù)的情況，實現(xiàn)不完整。

有了這些考慮，可以修改實現(xiàn)如下：

#include <iostream>
#include <cmath>

// 全局變量標記是否出錯
bool g_InvalidInput = false;
// 判斷值是否相等
bool equal(double num1, double num2);
// 求數(shù)值的正整數(shù)次方
double PowerWithUnsignedExponent(double base, unsigned int exponent);

double Power(double base, int exponent)
{
    g_InvalidInput = false;

    if(equal(base, 0.0) && exponent < 0)
    {
        g_InvalidInput = true;
        // 錯誤返回值為0
        return 0.0;
    }

    unsigned int absExponent = (unsigned int)(exponent);
    // 如果指數(shù)小于0，先變?yōu)檎龜?shù)
    if(exponent < 0)
        absExponent = (unsigned int)(-exponent);

    // 求n次方
    double result = PowerWithUnsignedExponent(base, absExponent);
    
    // 指數(shù)小于0，再求倒數(shù)
    if(exponent < 0) {
        result = 1.0/result;
    }

    return  result;
}

double PowerWithUnsignedExponent(double base, unsigned int exponent)
{
    double result = 1.0;
    for (int i = 1; i <= exponent; i++) {
        result *= base;
    }
    return  result;
}

bool equal(double num1, double num2)
{
    if ((num1 - num2 > -0.0000001) && (num1 - num2 < 0.0000001))
        return true;
    else
        return false;
}

上面實現(xiàn)時間復(fù)雜度為O(n)

思路2

思路1中，如果輸入指數(shù)exponent為32，則在函數(shù)PowerWithUnsignedExponent的循環(huán)中需要31次乘法。

為了進一步優(yōu)化，可以換一種思路考慮：我們的目標是求出一個數(shù)字的32次方，如果我們已經(jīng)知道了它的16次方，那么只要在16次方的基礎(chǔ)上再平方一次就可以了。而16次方是8次方的平方。這樣一次類推，我們求32次方只需要做5次乘法：先求平方，在平方的基礎(chǔ)上求4次方，在4次方的基礎(chǔ)上求8次方，在8次方的基礎(chǔ)上求16次方，最后在16次方的基礎(chǔ)上求32次方。

也就是說，可以有如下公式求a的n次方：

所以新的PowerWithUnsignedExponent函數(shù)代碼如下

double PowerWithUnsignedExponent(double base, unsigned int exponent)
{
    if (exponent == 0)
        return 1;
    if (exponent == 1)
        return base;

    // exponent >> 1 使用右移代替除以2
    double result = PowerWithUnsignedExponent(base, exponent >> 1);
    result *= result;
    // 是否是奇數(shù)
    if ((exponent & 0x1) == 1)
        result *= base;

    return result;
}

用位與運算符代替了求余運算符（%）來判斷一個數(shù)是奇數(shù)還是偶數(shù)。因為位運算的效率比乘除法及求余運算的效率要高很多。

時間復(fù)雜度為O(logn)

參考

《劍指offer》