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

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

题目：

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

看到了很多人会这样写：

public static double powerWithExponent(double base,int exponent){
		double result = 1.0;
		for(int i = 1; i <= exponent; i++){
			result = result * base;
		}
		return result;
	}

输入的指数(exponent)小于1即是零和负数时怎么办？

当指数为负数的时候，可以先对指数求绝对值，然后算出次方的结果之后再取倒数，当底数(base)是零且指数是负数的时候，如果不做特殊处理，就会出现对0求倒数从而导致程序运行出错。最后，由于0的0次方在数学上是没有意义的，因此无论是输出0还是1都是可以接受的。

public double power(double base, int exponent) throws Exception {
		double result = 0.0;
		if (equal(base, 0.0) && exponent < 0) {
			throw new Exception("0的负数次幂无意义");
		}
		if (equal(exponent, 0)) {
			return 1.0;
		}
		if (exponent < 0) {
			result = powerWithExponent(1.0 / base, -exponent);
		} else {
			result = powerWithExponent(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;
	}

	// 判断两个double型数据，计算机有误差
	private boolean equal(double num1, double num2) {
		if ((num1 - num2 > -0.0000001) && (num1 - num2 < 0.0000001)) {
			return true;
		} else {
			return false;
		}
	}

一个细节，再判断底数base是不是等于0时，不能直接写base==0，这是因为在计算机内表示小数时(包括float和double型小数)都有误差。判断两个数是否相等，只能判断 它们之间的绝对值是不是在一个很小的范围内。如果两个数相差很小，就可以认为它们相等。

还有更快的方法。

如果我们的目标是求出一个数字的32次方，如果我们已经知道了它的16次方，那么只要在16次方的基础上再平方一次就好了，依此类推，我们求32次方只需要做5次乘法。

我们可以利用如下公式：

private double powerWithExponent2(double base,int exponent){
		if(exponent == 0){
			return 1;
		}
		if(exponent == 1){
			return base;
		}
		double result = powerWithExponent2(base, exponent >> 1);
		result *= result;
		if((exponent&0x1) == 1){
			result *= base;
		}
		return result;
	}

我们用右移运算代替除2，用位与运算符代替了求余运算符（%)来判断一个数是奇数还是偶数。位运算的效率比乘除法及求余运算的效率要高很多。