《剑指offer》面试题16：数值的整数次方
题目：实现函数double Power(double base,int exponent)，求base的exponent次方。不能使用库函数，同时不需要考虑大数问题。
即全面又高效的解法：
当exponent为偶数时，例如exponent=32，如果我们已经知道了base的16次方，那么只需要在16次方的基础上再平方一次即可。而16次方是在8次方的基础上再平方一次...以此类推，求32次方只需要5次乘法：先求平方，在平方的基础上求4次方，在4次方的基础上求8次方，在8次方的基础上求16次方，在16次方的基础上求32次方。
当exponent为奇数时，例如exponent=33，如果我们已经知道了base的32次方，那么只需要在32次方的基础上再乘以base即可。而32次方是偶数的计算方法。
代码如下：
public static double Power(double base,int exponent) {
// 对0求倒数不合法
if (base == 0 && exponent < 0) {
throw new RuntimeException("input invalid");
}
// 0的0次方在数学上无意义
if (base == 0 && exponent == 0) {
return 0;
}
int absExponent = exponent < 0 ? -exponent : exponent;
double result = PowerCore(base,absExponent);
return exponent < 0 ? 1.0 / result : result;
}
private static double PowerCore(double base,int exponent) {
if (exponent == 0) {
return 1;
}
if (exponent == 1) {
return base;
}
// 右移运算符代替除以2
double result = PowerCore(base,exponent >> 1);
result *= result;
// 位与运算符判断奇数
if (exponent & 1 == 1) {
result = result * base;
}
return result;
}
