学步园

题目：实现函数double Power(double base, int exponent)，求base的exponent次方。不需要考虑溢出。

对二进制的操作很多人都不是很熟悉，因此编码可能觉得有些难度。我们可以换一种思路考虑：我们要求出一个数字的32次方，如果我们已经知道了它的16次方，那么只要在16次方的基础上再平方一次就可以了。而16次方是8次方的平方。这样以此类推，我们求32次方只需要做5次乘法：先求平方，在平方的基础上求4次方，在4次方的基础上平方求8次方，在8次方的基础上求16次方，最后在16次方的基础上求32次方。

也就是说，我们可以用如下公式求a的n次方：

这个公式很容易就能用递归来实现。新的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://zhedahht.blog.163.com/blog/static/254111742009101563242535/