递归快速幂

image-20210501085248070.png
代码很简单：

  1. /**
  2.  * @description: 递归快速幂
  3.  * @return {*} 幂运算的结果
  4.  * @param {*} a 底
  5.  * @param {*} n 幂
  6.  */
  7. function pow(a, n){
  8.     if (n == 0)
  9.         return 1;
  10.     else if (n % 2 == 1)
  11.         return pow(a, n - 1) * a;
  12.     else
  13.     {
  14.         let temp = pow(a, n / 2);
  15.         return temp * temp;
  16.     }
  17. }

非递归快速幂

v2-e99e321dcff33699093cde2876424dbe_1440w.jpg

  1. /**
  2.  * @description: 非递归快速幂
  3.  * @return {*} 幂运算的结果
  4.  * @param {*} a 底
  5.  * @param {*} n 幂
  6.  */
  7. function pow(a, n) {
  8.     let ans = 1;
  9.     while (n) {
  10.         // 如果n的当前末位为1
  11.         if (n & 1) {
  12.             ans = ans * a;
  13.         }
  14.         a = a * a;
  15.         n = n >> 1;
  16.     }
  17.     return ans;
  18. }