快速幂算法，可以将时间复杂度从O（N）降为O（log2N）。
比如要算2^n (n>0)，最简单的方法是：
int result = 0;
for (int i = 0; i < n; i++)
result *= 2;
时间复杂度是O（N）。
当n为偶数：
2^n = 2^(n/2) * 2^(n/2)
2^(n/2) = 2^(n/4) * 2^(n/4)
2^(n/4) = 2^(n/8) * 2^(n/8)
......
当n为奇数：
2^n = 2^(n/2) * 2^(n/2) * 2
2^(n/2) = 2^(n/4) * 2^(n/4)
2^(n/4) = 2^(n/8) * 2^(n/8)
推广为：
base^n = base^(n/2) * base^(n/2)；
base^n = base * base^((n-1)/2) * base^((n-1)/2)；
......
这样分解下去，就可以把时间复杂度降为O(log2N)。
现在可以用这个方法来实现pow函数:
double tiny_pow(double base, int n)
{
// 0的0次方极限趋近于1. 0^-1，0^-2会引起CPU异常，所以不作处理
if (equal(base, 0.0) && n == 0)
return 0.0;
unsigned int absN = ( n > 0 ? (unsigned int)n : abs(n) );
double result = powWithUnsignedN(base, absN);
if (n < 0)
result = 1.0 / result;
return result;
}
double powWithUnsignedN(double base, unsigned int n)
{
if (n == 0) return 1;
if (n == 1) return base; // 也是递归开始回溯的地方
double result = powWithUnsignedN(base, n >> 1);
result *= result ;
if (n & 1) // n为奇数
result *= base;
return result ;
}
bool equal(double num1, double num2)
{
// |num1 - num2| < 0.0000001
if (-0.0000001 < (num1 - num2) && (num1 - num2) < 0.0000001)
return true;
else
return false;
}
