数值的整数次方

【题目描述】

给定一个double类型的浮点数base和int类型的整数exponent。求base的exponent次方。

【解题思路】

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

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

【代码实现】

实现一：利用递归方式，但是容易堆栈溢出

 1 class Solution {
 2 public:
 3     double Power(double base, int exponent) {
 4         if(exponent==0)
 5             return 1;
 6         if(exponent==1)
 7             return base;
 8 
 9         int result=Power(base,exponent>>1);
10         result*=result;
11         if(exponent&0x1==1)
12             result*=base;
13 
14         return result;
15     }
16 };

实现二：（最佳实现）利用迭代实现快速幂运算

 1 class Solution {
 2 public:
 3     double Power(double base, int exponent) {
 4         int exp = abs(exponent);//如果不支持abs（）运算符，则改用“"int exp = exponent>0:exponent:-exponent;"
 5         double result = 1.0;
 6         while(exp){
 7         if(exp & 0x1) //判断指数是奇数还是偶数，如是奇数需要额外乘以一次底
 8                 result *= base;
 9             base *= base;
10             exp >>= 1;                  
11         }
12         return exponent < 0 ? 1/result :result;
13     }
14 };

实现三：（投机取巧的方式），呵呵，你知道的太多了……

1 class Solution {
2 public:
3     double Power(double base, int exponent) {
4        return Math.pow(base, exponent);
5     }
6 };