题目描述：
给定一个double类型的浮点数base和int类型的整数exponent。求base的exponent次方。不得使用库函数，同时不需要考虑大数问题。
不只要通过测试，要更着重代码的优化
测试用例：
base与exponent分别取正数、0、负数 共3*3九种情况
解题思路：
1）为base与exponent区分正数、0、负数 全面但是不够高效率的解法
class Solution {
public:
bool g_InvalidInput = false;
double Power(double base, int exponent) {
if(base==0 && exponent<=0){ //相等这是否有问题？？？ 修改为 abs(base-0.0)<10e-10
//0^0没有意义 而1/0 0不能为分母
g_InvalidInput = true; //用于标记是由于出错，返回0（此时该值为true）,若是由计算结果返回0，该值为false。
return 0.0;
}
double result = 1.0;
//确定是正值，用无符号比较好
unsigned int absExponent = (unsigned int)(exponent); //int到unsigned int要显示转换
if(exponent<0)
absExponent = (unsigned int)(-exponent);
/*if(exponent<0)
int absExponent = -exponent; //for处会显示没有定义absExponent变量
else
int absExponent = exponent;*/
for (int i=0;i<absExponent;i++) //有更高效的求解方法
result*=base;
if(exponent<0)
result=1.0/result; //用1.0比较好，而非1。 1也可以
return result;
}
};
注：[1] 对于double类型而言，由于精度的原因，不能用等号判断两个小数是否相等。因为double类型的表示往往是不精确的(近似表示)，有精度范围的那种。如果是运算结果，即使都是0.0，也不保证相等！一般用一个容差e(很小的值)。
[2] 上述代码采用全局变量 g_InvalidInput 来标识是否出错（函数返回0时，是由于计算结果为零，还是错误的输入）。但是在使用函数返回值时，如 double result = Power(2,3); 调用时，常常容易忘记检查 g_InvalidInput 以判断是否出错。
2）全面又高效的算法 时间复杂度O(logn)
当exponent=32时，要计算31次乘法。但是如果知道16的平方，再平方即可得到最终解。这样经过5次计算就可以得到最终解。
//实现1：递归调用
class Solution { public: bool g_InvalidInput = false; double Power(double base, int exponent) { if(abs(base-0.0)<10e-10 && exponent<=0){ //0^0没有意义 而1/0 0不能为分母 g_InvalidInput = true; //用于标记是由于出错，返回0（此时该值为true）,若是由计算结果返回0，该值为false。 return 0.0; } double result = 1.0; //确定是正值，用无符号比较好 unsigned int absExponent = (unsigned int)(exponent); //int到unsigned int要显示转换 if(exponent<0) absExponent = (unsigned int)(-exponent); /*if(exponent<0) int absExponent = -exponent; //for处会显示没有定义absExponent变量 else int absExponent = exponent;*/ for (int i=0;i<absExponent;i++) result*=base; if(exponent<0) result=1.0/result; //用1.0比较好，而非1。 1也可以 return result; } //改进的代码 double PowerWithUnsignedExponent(double base, unsigned int exponent){ if(exponent==0) //奇数终止 1/2=0 return 1; if(exponent==1) //偶数终止 2/2=1 return base;
//递归调用 double result = PowerWithUnsignedExponent( base, exponent>>1); //右移代替除以2 result*=result; if(exponent&0x1==1) //位与操作，最后一位是1，则一定是奇数。最后一位是0，则一定是偶数。 exponent%2==1 也可以判断，但是效率很低 result*=base; return result; } };
代码中的两处细节：判断base是否为0，以及用位运算代替乘除法以及取余运算。
位运算的效率比乘除法及求余运算的效率要高很多！！
//实现2：循环实现
class Solution {
public:
bool g_InvalidInput = false;
double Power(double base, int exponent) {
double result = 1,currBase = base;
int absExponent;
if(exponent>0){
absExponent = exponent;
}else if(exponent<0){
if(base==0.0){
g_InvalidInput = true;
return 0.0;
//throw new RuntimeException("分母不能为0");
}
absExponent = -exponent;
}else{// n==0
return 1;// 任何数的0次幂（包括0的0次方）。
}
//循环实现
while(absExponent!=0){
if((absExponent&1)==1) //奇数
result*=currBase;
currBase*=currBase;// 翻倍，记录的是基数
absExponent>>=1;// 右移一位，除以2
}
return exponent>=0?result:(1/result);
}
};
指数计算：
- 当n为偶数，a^n =（a^n/2）*（a^n/2）
- 当n为奇数，a^n = a^[(n-1)/2] * a^[(n-1)/2] * a
- 2^11 = 2^1 * 2^2 * 2^8 //其中11的二进制表示位 ：1011 将其拆分为：1000 和 0010 和 0001
- 2^1011 = 2^0001 * 2^0010 * 2^1000