你的分享就是我们的动力 ---﹥

程序员面试题精选100题(44)-数值的整数次方[算法]

时间:2014-11-28 17:37来源:www.chengxuyuans.com 点击:
题目:实现函数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;

}

转载注明地址:http://www.chengxuyuans.com/job_interview/85144.html