题目描述

实现 pow(x,n) ，即计算 x 的 n 次幂函数，50. Pow(x, n) - 图1

分析

快速幂算法

  1. //递归算法
  2. class Solution {
  3. public:
  4.     double quickMul(double x, long long N) {
  5.         if (N == 0) {
  6.             return 1.0;
  7.         }
  8.         double y = quickMul(x, N / 2);
  9.         return N % 2 == 0 ? y * y : y * y * x;
  10.     }
  12.     double myPow(double x, int n) {
  13.         long long N = n;
  14.         return N >= 0 ? quickMul(x, N) : 1.0 / quickMul(x, -N);
  15.     }
  16. };

迭代算法利用到了x的二进制数据
77=1001101b

  1. //迭代算法
  2. class Solution {
  3. public:
  4.     double quickMul(double x, long long N) {
  5.         double ans = 1.0;
  6.         // 贡献的初始值为 x
  7.         double x_contribute = x;
  8.         // 在对 N 进行二进制拆分的同时计算答案
  9.         while (N > 0) {
  10.             if (N % 2 == 1) {
  11.                 // 如果 N 二进制表示的最低位为 1，那么需要计入贡献
  12.                 ans *= x_contribute;
  13.             }
  14.             // 将贡献不断地平方
  15.             x_contribute *= x_contribute;
  16.             // 舍弃 N 二进制表示的最低位，这样我们每次只要判断最低位即可
  17.             N /= 2;
  18.         }
  19.         return ans;
  20.     }
  22.     double myPow(double x, int n) {
  23.         long long N = n;
  24.         return N >= 0 ? quickMul(x, N) : 1.0 / quickMul(x, -N);
  25.     }
  26. };