數值的整數次方——11

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

    首先可以想到的是，如果exponent是個大于零的數，可用循環來進行相乘，而如果exponent是個復數，依然可以將base進行相乘，最后再取其倒數也就是用1去除以相乘結果。程序設計如下：

#include <iostream>
#include <math.h>
using namespace std;

double my_pow(double base, int exp)
{
    if(exp == 0)//當exp為0的時候，不論base為多少結果都為1
        return 1;
    if((base == 0) || (base == 1))//當base為0或者1的時候不論exp為多少結果都為base
        return base;

    double ret = 1.0;
    int flag = 1;//設定標志位，判斷exp的正負性
    if(exp < 0)
    {
        flag = 0;
        exp *= (-1);
    }
    while(exp--)
    {
        ret *= base;
    }
    if(flag == 0)
        ret = 1/ret;
    return ret;
}

int main()
{
    double base = 6.123784;
    int exp = -5;
    double ret = my_pow(base, exp);
    cout<<"my_pow ret: "<<ret<<endl;
    cout<<"pow ret: "<<pow(base, exp)<<endl;
    return 0;
}

上面的栗子中，為了驗證結果的正確性與否在輸出結果的比較中調用了庫函數的pow來進行比較，運行程序得結果：

    但是上面的代碼還是有可優化的成分的，比如如果exp的值比較大，那么循環的次數也就比較多，這個時間復雜度就為O(N)，如果exp的值為100的話，那么其實，當循環乘到50的時候，只需要再乘上一個50就能得到結果，而不需要再循環50次，而50又可以由相乘25次的結果再自乘一次得到，而25次的結果又可以由12次的結果乘以自身再乘一個base而得到......因此，將上面的代碼改為如下：

double GetPow(double base, int exp)
{
    double ret = 1;
    if(exp != 0)
    {   
        ret = GetPow(base, exp>>1);
        if((exp & 0x1) == 0)
        {
            ret *= ret;
        }
        else
        {
            ret *= (ret * base);
        }   
    }   
    return ret;
}

double my_pow(double base, int exp)
{ 
    if((base == 0) || (base == 1)) 
        return base;

    int flag = 1;
    if(exp < 0)
    {   
        flag = 0;
        exp *= (-1);
    }   

    double ret = GetPow(base, exp);

    if(flag == 0)
        ret = 1/ret;
    return ret;
}

解釋一下上面的GetPow函數，因為前面說可以將循環次數減少，比如100次方可以求50次方再平方，50次方可以求25次方再平方......以此類推，其實就是100->50->25->12(+1)->6->3->1(+1)->0，而我們從最低位倒著算起，base的0次方->base的1次方->base的3次方->base的6次方->base的12次方->......這樣可以發現，其實就是在exponent的二進制表示位上進行的操作，從最高位到最低位，當比特位值為1時，就將前面的結果相乘再乘上一個base也就是上面的（+1），如果比特位值為0，就直接將前面的結果相乘......而從高位到低位就需要用遞歸來獲取；

運行程序，結果和pow庫函數相同。

《完》