50. Pow(x, n)

实现 pow(x, n) ，即计算 x 的 n 次幂函数。 示例 1:

  1. 输入: 2.00000, 10
  2. 输出: 1024.00000

示例 2:

  1. 输入: 2.10000, 3
  2. 输出: 9.26100

示例 3:

  1. 输入: 2.00000, -2
  2. 输出: 0.25000
  3. 解释: 2-2 = 1/22 = 1/4 = 0.25

说明:

  • -100.0 < x < 100.0
  • n 是 32 位有符号整数，其数值范围是 [−231, 231 − 1] 。

代码实现

  1. #include<math.h>
  3. /*
  4.     快速幂迭代版，时间复杂度O(logn)
  5.     求 a^n
  6. */
  7. double pow_iteration(double a,long long n)
  8. {
  9.     double pow = 1.0;//最后结果
  10.     double p = a;//每次乘的因子
  11.     while(0 < n)
  12.     {
  13.         if(n&1) // 等效于n % 2 == 1，即n为奇数 
  14.           pow *= p;
  15.         p *= p;
  16.         n >>= 1;//等效于n = n / 2
  17.     }
  18.     return pow;
  19. }
  21. double myPow(double x, long long n){
  22.     double res=1.0;
  23.     long long cnt = n;
  24.     if(n <0 )
  25.         cnt = labs((long long)n);
  27.     res = pow_iteration(x,cnt);
  29.     if(n <0 )
  30.         res = 1.0/res;
  31.     return res;
  32. }