Question

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

我们都知道在C语言的库中有一个pow函数可以用来求乘方，本题要求实现类似于pow的功能。要求实现特定库函数（特别是处理数值和字符串的函数）的功能，是一类常见的面试题。在本书收集的面试题中，除了这个题目外，还有面试题49把字符串转换成整数要求实现库函数atoi的功能。这就要求我们平时编程的时候除了能熟练使用库函数外，更重要的是要理解库函数的实现原理。

自以为题目简单的解法

由于不需要考虑大数问题，这道题看起来很简单，可能不少应聘者在看到题目30秒后就能写出如下的代码：

不过遗憾的是，写得快不一定就能得到面试官的青睐，因为面试官会问要是输入的指数（exponent）小于1即是零和负数的时候怎么办？上面的代码完全没有考虑，只包括了指数是正数的情况。

全面但不够高效的解法，我们离Offer已经很近了

我们知道当指数为负数的时候，可以先对指数求绝对值，然后算出次方的结果之后再取倒数。既然有求倒数，我们很自然就要想到有没有可能对0求倒数，如果对0求倒数怎么办？当底数（base）是零且指数是负数的时候，如果不做特殊处理，就会出现对0求倒数从而导致程序运行出错。怎么告诉函数的调用者出现了这种错误？前面提到我们可以采用3种方法：返回值、全局代码和异常。面试的时候可以向面试官阐述每种方法的优缺点，然后一起讨论决定选用哪种方式。

最后需要指出的是，由于0的0次方在数学上是没有意义的，因此无论是输出0还是1都是可以接受的，但这都需要和面试官说清楚，表明我们已经考虑到这个边界值了。

有了这些相对而言已经全面很多的考虑，我们就可以把最初的代码修改如下：

在上述代码中我们采用全局变量来标识是否出错。如果出错了，则返回的值是0。但为了区分是出错的时候返回的0，还是底数为0的时候正常运行返回的0，我们还定义了一个全局变量g_InvalidInput。当出错时，这个变量被设为true，否则为false。这样做的好处是，我们可以把返回值直接传递给其他变量，比如写double result=Power（2,3），也可以把函数的返回值直接传递给其他需要double型参数的函数。但缺点是这个函数的调用者有可能会忘记去检查g_InvalidInput以判断是否出错，留下了安全隐患。由于有优点也有缺点，因此我们在写代码之前要和面试官讨论采用哪种出错处理方式最合适。

一个细节值得我们注意：在判断底数base是不是等于0时，不能直接写base==0，这是因为在计算机内表示小数时（包括float和double型小数）都有误差。判断两个小数是否相等，只能判断它们之差的绝对值是不是在一个很小的范围内。如果两个数相差很小，就可以认为它们相等。这就是我们定义函数equal的原因。

面试小提示：

由于计算机表示小数（包括float和double型小数）都有误差，我们不能直接用等号（==）判断两个小数是否相等。如果两个小数的差的绝对值很小，比如小于0.0000001，就可以认为它们相等。

此时我们考虑得已经很周详了，已经能够达到很多面试官的要求了。但是如果我们碰到的面试官是一个在效率上追求完美的人，那么他有可能会提醒我们函数PowerWithUnsignedExponent还有更快的办法。

全面又高效的解法，确保我们能拿到Offer

如果输入的指数exponent为32，我们在函数PowerWithUnsignedExponent的循环中需要做31次乘法。但我们可以换一种思路考虑：我们的目标是求出一个数字的32次方，如果我们已经知道了它的16次方，那么只要在16次方的基础上再平方一次就可以了。而16次方是8次方的平方。这样以此类推，我们求32次方只需要做5次乘法：先求平方，在平方的基础上求4次方，在4次方的基础上求8次方，在8次方的基础上求16次方，最后在16次方的基础上求32次方。

也就是说，我们可以用如下公式求a的n次方：

这个公式看起来是不是眼熟？我们前面在介绍用O（logn）时间求斐波那契数列时，就讨论过这个公式，这个公式很容易就能用递归来实现。新的PowerWithUnsignedExponent代码如下：

最后再提醒一个细节：我们用右移运算符代替了除以2，用位与运算符代替了求余运算符（%）来判断一个数是奇数还是偶数。位运算的效率比乘除法及求余运算的效率要高很多。既然要优化代码，我们就把优化做到极致。

在面试的时候，我们可以主动提醒面试官注意代码中的两处细节（判断base是否等于0和用位运算替代乘除法及求余运算），让他知道我们对编程的细节很重视。细节很重要，因为细节决定成败，一两个好的细节说不定就能让面试官下定决心给我们Offer。

源代码：

本题完整的源代码详见11_Power项目。

测试用例：

把底数和指数分别设为正数、负数和零。

本题考点：

- 考查思维的全面性。这个问题本身不难，但能顺利通过的应聘者不是很多。有很多人会忽视底数为0而指数为负数时的错误处理。

- 对效率要求比较高的面试官还会考查应聘者快速做乘方的能力。