剑指Offer面试题11（Java版）：数值的整数次方

喜欢ヅ旅行 2023-10-17 17:43 28阅读 0赞

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

**1、自以为很简单的解法：**

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

**\[java\]** [view plain][] [copy][view plain]

1.  publicdouble powerWithExponent(double base,int exponent)\{ 
2.  double result = 1.0; 
3.  for(int i = 1;i<= exponent;i++)\{ 
4.   result = result\*base; 
5.   \} 
6.  return result; 
7.   \}

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

**2、全面但不够高效的解法，我们离Offer已经不远了**

我们知道当指数为负数的时候，可以先对指数求绝对值，然后算出次方的结果之后再取倒数。既然有求倒数，我们很自然的就要想到有没有可能对0求倒数，如果对0求倒数怎么办？当底数base是零且指数是负数的时候，我们不做特殊的处理，就会发现对0求倒数从而导致程序运行出错。怎么告诉函数的调用者出现了这种错误？在Java中可以抛出异常来解决。

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

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

**\[java\]** [view plain][] [copy][view plain]

1.  /\*\*
2.   \* 题目：实现函数double Power(double base,int exponent),求base的exponent次方。不得使用库函数，同时不需要考虑大数问题
3.   \* 对于这道题，要考虑四种情况：
4.   \* 1、底数为0，指数为负数的情况，无意义
5.   \* 2、指数为0，返回1
6.   \* 3、指数为负数，返回1.0/base,-exponent
7.   \* 4、指数正数，base,exponent
8.   \*/
9.  package swordForOffer; 
10. 
11. /\*\*
12.  \* @author JInShuangQi
13.  \*
14.  \* 2015年7月30日
15.  \*/
16. publicclass E11Power \{ 
17. 
18. publicdouble power(double base,int exponent) throws Exception\{ 
19. double result = 0.0; 
20. if(equal(base,0.0) && exponent<0)\{ 
21. thrownew Exception("0的负数次幂无意义"); 
22.  \} 
23. if(equal(exponent,0))\{ 
24. return1.0; 
25.  \} 
26. if(exponent <0)\{ 
27.  result= powerWithExponent(1.0/base, -exponent); 
28.  \} 
29. else\{ 
30.  result = powerWithExponent(base,exponent); 
31.  \} 
32. return result; 
33.  \} 
34. privatedouble powerWithExponent(double base,int exponent)\{ 
35. double result = 1.0; 
36. for(int i = 1;i<= exponent;i++)\{ 
37.  result = result\*base; 
38.  \} 
39. return result; 
40.  \} 
41. //判断两个double型数据，计算机有误差
42. privateboolean equal(double num1,double num2)\{ 
43. if((num1-num2>-0.0000001) && (num1-num2<0.0000001))\{ 
44. returntrue; 
45.  \}else\{ 
46. returnfalse; 
47.  \} 
48.  \} 
49. publicstaticvoid main(String\[\] args) throws Exception\{ 
50.  E11Power test = new E11Power(); 
51.  System.out.println(test.power(3, -1)); 
52.  \} 
53. \}

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

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

**3、全面而高效的解法，确保我们能拿到Offer**

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

也就是说我们可以利用下面这个公示求a的n次方：

![20150731084039653][]

这个公式就是我们前面利用O(logn)时间求斐波那契数列时，讨论的公式，这个公式很容易就能用递归实现。新的PowerWithExponent代码如下：

**\[java\]** [view plain][] [copy][view plain]

1.  privatedouble powerWithExponent2(double base,int exponent)\{ 
2.  if(exponent == 0) 
3.  return1; 
4.  if(exponent == 1) 
5.  return base; 
6.  double result = powerWithExponent2(base,exponent >>1); 
7.   result \*= result; 
8.  if((exponent&0x1) == 1) 
9.   result \*=base; 
10. return result; 
11.  \}

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

[view plain]: http://blog.csdn.net/jsqfengbao/article/details/47164537#
[20150731084039653]: https://img-blog.csdn.net/20150731084039653