题目
实现函数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》
