剑指Offer面试题11数值的整数次方

面试题11：数值的整数次方

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

注意：判断两个小数是否相等不能用==，因为计算机表示小数有误差，我们只能判断它们差的绝对值是否在一个很小的范围内。

题外话：程序错误处理的三种方法：返回值、全局变量、异常。返回值好处是根据返回值判断错误原因，缺点是函数只能返回一个值，使用不便。全局变量不会占用函数返回结果。异常更清晰明了，但有些语言不支持。

本题一般思路的java实现如下：

public class Power {	PRivate double power(double base,int exponent) throws Exception{		double result = 0.0;		if(equal(base,0.0) && exponent<0){			throw new Exception("0的负数次幂无意义");		}		if(exponent == 0){//其中0的0次方没有意义，返回0或1都可以			return 1.0;		}		if(exponent > 0){			result = powerWithExponent(base, exponent);		}else{//负数次幂			result = powerWithExponent(1.0/base, -exponent);		}		return result;	}	//计算结果	private double powerWithExponent(double base,int exponent){		double result = 1.0;		for(int i=1;i<=exponent;i++){			result = result * base;		}		return result;	}	//判断两个小数是否相等	private boolean equal(double num1,double num2){		if( ((num1-num2) > -0.0000001) && (num1-num2) < 0.0000001 ){			return true;		}else return false;	}	public static void main(String[] args) throws Exception {		Power test = new Power();		System.out.println(test.power(2, 3));	}}但以上程序的计算过程并不是效率最高的，因为假如求32次方，要循环31次，但如果我们已经求出了16次方，再平方一次就好了，而16可以由8再平方，以此类推。
归纳为当n为偶数时，a^n=a^(n/2)*a^(n/2)，n为奇数时，a^n=a^((n-1)/2)*a^((n-1)/2)*a，计算量会减少，可以用递归实现，复杂度从O(n)变成了O(logn)。
细节：用右移运算符代替除以2，用与运算符代替取余来判断奇偶，因为位运算符效率高很多。程序如下：
private double powerWithExponent2(double base,int exponent){	if(exponent == 0) return 1;	if(exponent == 1) return base;//两个递归终止的条件	double result = powerWithExponent2(base, exponent >> 1);//用右移1位代替除2	result *= result;	if( (exponent & 1) == 1) result *= base;//二进制最低位为1，则为奇数	return result;	//以输入（2，6）为例进行说明：开始后，进入第一次递归，输入为（2，3）	//然后进入第二次递归，输入为（2，1），此时exponent为1，返回base为2，也就是说第二次递归的执行结果为2	//然后回到了第一次递归，里头的result值为第二次递归的结果2，然后向下执行，result为2*2，第一次递归时exponent为3，result=4*2，返回8	//所以第一次递归的执行结果为8，然后回到原函数，里头的result为8，然后执行8*8，此时exponent为6，最终结果就是64。}