本文共 967 字，大约阅读时间需要 3 分钟。

我们接触幂运算都是来自于那个著名的传说——国王的米粒棋盘游戏。在这个传说里，最为核心的就是越往后计算量越大。所以，在求解幂运算的时候，降低时间复杂度就很关键。

本文主要采用了快速幂算法和位运算来进行优化。 如果采用传统的的逐项相乘的方法，虽然可以通过算例，但是时间复杂度为O(n)。

double Power(double base, int exponent) {
   	double result=1;	if(base==0)		return 0;	else if(exponent ==0)		return result;	else if(exponent >0)	{
       for(int i=0;i

耗时3ms，内存占用592k。

快速幂运行就是通过增大底数来缩小指数的方法。例如求10的100次方，可以写为100的50次方，那么100次循环就降为了50次。所以快速幂算法的时间复杂度为O(logn)。 进一步的，在取余和除以2的时候，可以使用位运算来代替。 取余即为与1相与，1是000…1，相与结果即为最后一位。与2相除即为右移一位，而且还是整数除法，因为最后一位的1会被舍去。

double result=1;	if(base==0)		return 0;	else if(exponent ==0)		return result;	else if(exponent >0)	{
          while(exponent >0)	   {
   		if(exponent &1)		    result*=base;			base*=base;			exponent >>=1;				   }	}	else if(exponent <0)	{
   	   exponent =-exponent ;	    while(exponent >0)		{
   		if(exponent &1)		    result*=base;			base*=base;			exponent >>=1;		}		result =1.0/result ;	}		return result;

代码中在指数取余为1时，结果才会与底数相乘，不过显然循环的最后一步指数一定是1，所以最后前n项积一定会与底数相乘。

转载地址：http://gndmi.baihongyu.com/