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


首先可以想到的是，如果exponent是个大于零的数，可用循环来进行相乘，而如果exponent是个复数，依然可以将base进行相乘，最后再取其倒数也就是用1去除以相乘结果。程序设计如下：

#include<iostream>#include<math.h>usingnamespacestd;doublemy_pow(doublebase,intexp){if(exp==0)//当exp为0的时候，不论base为多少结果都为1return1;if((base==0)||(base==1))//当base为0或者1的时候不论exp为多少结果都为basereturnbase;doubleret=1.0;intflag=1;//设定标志位，判断exp的正负性if(exp<0){flag=0;exp*=(-1);}while(exp--){ret*=base;}if(flag==0)ret=1/ret;returnret;}intmain(){doublebase=6.123784;intexp=-5;doubleret=my_pow(base,exp);cout<<"my_powret:"<<ret<<endl;cout<<"powret:"<<pow(base,exp)<<endl;return0;}


上面的栗子中，为了验证结果的正确性与否在输出结果的比较中调用了库函数的pow来进行比较，运行程序得结果：


但是上面的代码还是有可优化的成分的，比如如果exp的值比较大，那么循环的次数也就比较多，这个时间复杂度就为O(N)，如果exp的值为100的话，那么其实，当循环乘到50的时候，只需要再乘上一个50就能得到结果，而不需要再循环50次，而50又可以由相乘25次的结果再自乘一次得到，而25次的结果又可以由12次的结果乘以自身再乘一个base而得到......因此，将上面的代码改为如下：

doubleGetPow(doublebase,intexp){doubleret=1;if(exp!=0){ret=GetPow(base,exp>>1);if((exp&0x1)==0){ret*=ret;}else{ret*=(ret*base);}}returnret;}doublemy_pow(doublebase,intexp){if((base==0)||(base==1))returnbase;intflag=1;if(exp<0){flag=0;exp*=(-1);}doubleret=GetPow(base,exp);if(flag==0)ret=1/ret;returnret;}


解释一下上面的GetPow函数，因为前面说可以将循环次数减少，比如100次方可以求50次方再平方，50次方可以求25次方再平方......以此类推，其实就是100->50->25->12(+1)->6->3->1(+1)->0，而我们从最低位倒着算起，base的0次方->base的1次方->base的3次方->base的6次方->base的12次方->......这样可以发现，其实就是在exponent的二进制表示位上进行的操作，从最高位到最低位，当比特位值为1时，就将前面的结果相乘再乘上一个base也就是上面的（+1），如果比特位值为0，就直接将前面的结果相乘......而从高位到低位就需要用递归来获取；

运行程序，结果和pow库函数相同。



《完》