剑指offer - 数值的整数次方

题目

实现函数double Power(double base, int exponent)，求base的exponent次方。不得使用库函数，同时不需要考虑大数问题

思路1

由于不需要考虑大数问题，实现很简单，如下

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

但是我们少考虑了一些情况，比如：如果输入指数（exponent）是零和负数的时候怎么办？如果底数（base）是零怎么办？这些情况都没有处理，上面的代码只考虑了指数是正数的情况，实现不完整。

有了这些考虑，可以修改实现如下：

#include <iostream>
#include <cmath>

// 全局变量标记是否出错
bool g_InvalidInput = false;
// 判断值是否相等
bool equal(double num1, double num2);
// 求数值的正整数次方
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);
    // 如果指数小于0，先变为正数
    if(exponent < 0)
        absExponent = (unsigned int)(-exponent);

    // 求n次方
    double result = PowerWithUnsignedExponent(base, absExponent);
    
    // 指数小于0，再求倒数
    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;
}

上面实现时间复杂度为O(n)

思路2

思路1中，如果输入指数exponent为32，则在函数PowerWithUnsignedExponent的循环中需要31次乘法。

为了进一步优化，可以换一种思路考虑：我们的目标是求出一个数字的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;

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

    return result;
}

用位与运算符代替了求余运算符（%）来判断一个数是奇数还是偶数。因为位运算的效率比乘除法及求余运算的效率要高很多。

时间复杂度为O(logn)

参考

《剑指offer》