11.md

剑指Offer之面试题11：数值的整数次方(power)

本章的主题是高质量的代码，因此，虽然表面上看，本章的题目不是很难，但是，写出好的代码却也不容易。

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

1 方法1：常规思维

double Power(double base, int exponent)
{
	double result = 1.0;

	for(int i = 1; i <= exponent; ++i) {
		result *= base;
	}

	return result;
}

这是很常规的方法，Power的意义就是exponent个base的乘积。

但是，其中有几个问题没有考虑：

• 如果exponent为负数呢？(特殊情况)
• 如果考虑了负数，base为0呢？(异常情况)

2 方法2：考虑非常规情况

bool equal(double num1, double num2)
{
	if((num1 - num2 > -0.0000001) && (num1 - num2 < 0.0000001)) {
		return true;
	}

	return false;
}

double power_unsigned(double base, unsigned int exponent)
{
	double result = 1.0;

	for(unsigned int i = 1; i <= exponent; ++i) {
		result *= base;
	}

	return result;
}

double Power(double base, int exponent)
{
	if(equal(base, 0.0) && exponent < 0) {
		throw string("bad parameter");
	}

	unsigned int abs_exponent = (unsigned int)exponent;
	if(exponent < 0) {
		abs_exponent = (unsigned int)(-exponent);
	}

	double result = power_unsigned(base, abs_exponent);
	if(exponent < 0) {
		result = 1.0 / result;
	}

	return result;
}

要点：

• 判断底数为0。由于底数的类型是double，不能像整型那样直接用==进行比较，而是只要两个double类型的差值在一个很小的范围(精度)内就可以说明两个double类型是相等的。这就是equal的功能。
• 底数和指数同时为0。数学上，底数和指数同时为0是没有意义的，我们不会使用这样的值，因此，书上说无论输出0还是1都是可以接受的，书上的代码返回1。也可以抛出异常。
• 异常处理。书上的代码用一个标志变量g_InvalidInput来表示结果是否有效，这里我使用的是C++的异常处理机制。

3 方法3

利用公式重写power_unsigned函数：

a^n = a^(n/2) * a^(n/2) n为偶数

a^n = a^((n-1)/2) * a^((n-1)/2) n为奇数

double power_unsigned(double base, unsigned int exponent)
{
	if(exponent == 0) {
		return 1;
	}

	if(exponent == 1) {
		return base;
	}

	double result = power_unsigned(base, exponent >> 1);
	result *= result;

	if(exponent & 1 == 1) {
		result *= base;
	}

	return result;
}

要点：

• 递归。
• 用右移位运算代替除以2。
• 用位运算判断奇偶性。