二分求幂,最初是在剑指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; }