二分求幂（pow的logn算法）

二分求幂，最初是在剑指offer上看到，书中给出了递归的代码，后来在王道机试指南上再次看到，那上面给出了非递归的代码。

二分求幂的原理如图：

剑指offer上的递归代码如下：

double powerWithUnsignedExponent(double base,unsigned int exponent)
{
	if(exponent==0)
		return 1;
	if(exponent==1)
		return base;
	double result=powerWithUnsignedExponent(base,exponent>>1);//exponent>>1即exponent/2 
	result*=result;
	if(exponent & 0x1==1)//a & 0x1相当于a%2 
		result*=base;
	return result;
}

王道书上的非递归代码如下：

int power(int a,int b)
{
	int ans=1;
	while(b!=0)
	{
		if(b%2==1)
			ans*=a;
		b/=2;
		a*=a;
	}
	return ans;
}

转载自原文链接, 如需删除请联系管理员。

原文链接：二分求幂（pow的logn算法），转载请注明来源！