面试题16:数值的整数次方

题目

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

解题思路

• 方法一

1. 考虑指数为负数时，应先把指数取绝对值，然后对计算结果取倒数。
2. 考虑特殊情况比如:base=0和exponent=0的情况。

• 方法二
  考虑若输入的指数exponent为32，则在函数power的循环中需要做31次乘法。换一种思路考虑:目标是求出一个数字的32次方，若知道它的16次方，那么只要在16次方的基础上再平放一次就好，而10次方是8次方的平方。以此类推，求32次方只需要5次乘法。

  
  
  image.png

代码

• 细节
  设置标志位，记录当指数为负数时需要对结果取倒数。

class Solution{
  public:
        double Power(double base,int exponent)
        {
            double result = 1.0;
            bool flag = true;
            if(base == 0)     return 0;
            if(exponent == 0) return 1;
            if(exponent < 0)
            {
                flag = false;
                exponent = -1 * exponent;
            }
            for(int i = 0;i < exponent;i++)
            {
                result = result * base;
            }
            if(flag == false)
            {
                result = 1.0/result;
            }
            return result;
        }
};

• 方法二
  细节
  用右移运算符代替除以2，用位与运算符代替求余运算符来判断一个数是奇数还是偶数。这种方式比乘除法及求余效率高很多。

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

            double result = Power_1(base,exponent >> 1);

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

完整代码见Github