程序員面試題精選100題(44)-數值的整數次方[算法]

時間:2019-09-22 編輯:范文亭
題目:實現函數double Power(double base, int exponent),求base的exponent次方。不需要考慮溢出。
分析:這是一道看起來很簡單的問題。可能有不少的人在看到題目后30秒寫出如下的代碼:
double Power(double base, int exponent)
{
      double result = 1.0;
      for(int i = 1; i <= exponent; ++i)
            result *= base;
 
      return result;
}
 
上述代碼至少有一個問題:由于輸入的exponent是個int型的數值,因此可能為正數,也可能是負數。上述代碼只考慮了exponent為正數的情況。
接下來,我們把代碼改成:
bool g_InvalidInput = false;
 
double Power(double base, int exponent)
{
    g_InvalidInput = false;
 
    if(IsZero(base) && exponent < 0)
    {
        g_InvalidInput = true;
        return 0.0;
    }
 
    unsigned int unsignedExponent = static_cast<unsigned int>(exponent);
    if(exponent < 0)
        unsignedExponent = static_cast<unsigned int>(-exponent);
 
    double result = PowerWithUnsignedExponent(base, unsignedExponent);
    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;
}
 
上述代碼較之前的代碼有了明顯的改進,主要體現在:首先它考慮了exponent為負數的情況。其次它還特殊處理了當底數base為0而指數exponent為負數的情況。如果沒有特殊處理,就有可能出現除數為0的情況。這里是用一個全局變量來表示無效輸入。關于不同方法來表示輸入無效的討論,詳見本系列第17題
最后需要指出的是:由于0^0次方在數學上是沒有意義的,因此無論是輸入0還是1都是可以接受的,但需要在文檔中說明清楚。
這次的代碼在邏輯上看起來已經是很嚴密了,那是不是意味了就沒有進一步改進的空間了呢?接下來我們來討論一下它的性能:
如果我們輸入的指數exponent為32,按照前面的算法,我們在函數PowerWithUnsignedExponent中的循環中至少需要做乘法31次。但我們可以換一種思路考慮:我們要求出一個數字的32次方,如果我們已經知道了它的16次方,那么只要在16次方的基礎上再平方一次就可以了。而16次方是8次方的平方。這樣以此類推,我們求32次方只需要做5次乘法:求平方,在平方的基礎上求4次方,在4次方的基礎上平方求8次方,在8次方的基礎上求16次方,最后在16次方的基礎上求32次方。
32剛好是2的整數次方。如果不巧輸入的指數exponent不是2的整數次方,我們又該怎么辦呢?我們換個數字6來分析,6就不是2的整數次方。但我們注意到6是等于2+4,因此我們可以把一個數的6次方表示為該數的平方乘以它的4次方。于是,求一個數的6次方需要3次乘法:第一次求平方,第二次在平方的基礎上求4次方,最后一次把平方的結果和4次方的結果相乘。
現在把上面的思路總結一下:把指數分解了一個或若干個2的整數次方。我們可以用連續平方的方法得到以2的整數次方為指數的值,接下來再把每個前面得到的值相乘就得到了最后的結果。
到目前為止,我們還剩下一個問題:如何將指數分解為一個或若干個2的整數次方。我們把指數表示為二進制數再來分析。比如6的二進制表示為110,在它的第2位和第3位為1,因此6=2^(2-1)+2^(3-1) 。也就是說只要它的第n位為1,我們就加上2的n-1次方。
最后,我們根據上面的思路,重寫函數PowerWithUnsignedExponent:
 
double PowerWithUnsignedExponent(double base, unsigned int exponent)
{
    std::bitset<32> bits(exponent);
    if(bits.none())
        return 1.0;
 
    int numberOf1 = bits.count();
    double multiplication[32];
    for(int i = 0; i < 32; ++i)
    {
        multiplication[i] = 1.0;
    }
 
    // if the i-th bit in exponent is 1,
    // the i-th number in array multiplication is base ^ (2 ^ n)
    int count = 0;
    double power = 1.0;
    for(int i = 0; i < 32 && count < numberOf1; ++i)
    {
        if(i == 0)
            power = base;
        else
            power = power * power;
 
        if(bits.at(i))
        {
            multiplication[i] = power;
            ++count;
        }
    }
 
    power = 1.0;
    for(int i = 0; i < 32; ++i)
    {
        if(bits.at(i))
            power *= multiplication[i];
    }
 
    return power;
}
 
       在上述代碼中,我們用C++的標準函數庫中bitset把整數表示為它的二進制,增大代碼的可讀性。如果exponent的第i位為1,那么在數組multiplication的第i個數字中保存以base為底數,以2的i次方為指數的值。最后,我們再把所以位為1在數組中的對應的值相乘得到最后的結果。
 
上面的代碼需要我們根據base的二進制表達的每一位來確定是不是需要做乘法。對二進制的操作很多人都不是很熟悉,因此編碼可能覺得有些難度。我們可以換一種思路考慮:我們要求出一個數字的32次方,如果我們已經知道了它的16次方,那么只要在16次方的基礎上再平方一次就可以了。而16次方是8次方的平方。這樣以此類推,我們求32次方只需要做5次乘法:先求平方,在平方的基礎上求4次方,在4次方的基礎上平方求8次方,在8次方的基礎上求16次方,最后在16次方的基礎上求32次方。
也就是說,我們可以用如下公式求a的n次方:
程序員面試題精選100題(44)-數值的整數次方 - 何海濤 - 微軟、Google等面試題
這個公式很容易就能用遞歸來實現。新的PowerWithUnsignedExponent代碼如下:
double PowerWithUnsignedExponent(double base, unsigned int exponent)
{
    if(exponent == 0)
        return 1;
    if(exponent == 1)
        return base;
 
    double result = PowerWithUnsignedExponent(base, exponent >> 1);
    result *= result;
    if(exponent & 0x1 == 1)
        result *= base;
 
    return result;
}
本文已影響
相關文章
大亨pk10计划苹果版