leetcode-50. Pow(x, n) · 快速幂

题面

给定x, n, 求pow(x, n)。

样例

Example 1:
Input: 2.00000, 10
Output: 1024.00000
Example 2:
Input: 2.10000, 3
Output: 9.26100
Example 3:
Input: 2.00000, -2
Output: 0.25000
Explanation: 2-2 = 1/22 = 1/4 = 0.25
Note:

-100.0 < x < 100.0

n is a 32-bit signed integer, within the range [−231, 231 − 1] 要小心。

思路1

暴力遍历，累积

时间复杂度：O(n)

👉超时

 1 class Solution {
 2 public:
 3     double myPow(double x, int n) {
 4         if(n == 0)
 5             return 1;
　　　　　　 res = 1;
 6         else if(n > 0)
 7         {
 8             while(n--)
 9             {
10                 res *= x;
11             }
12             return res;
13         }
14         else
15         {
16             while(n++)
17             {
18                 res *= x;
19             }
20             return 1.0/x;
21         }
22     }
23 };

思路2 : 快速幂

时间复杂度：O(log₂n)

算法原理

快速幂的快速在于它保存了上一步的计算结果。

关于abs(), fabs(), labs(), llabs()，参考这里

我们举例说明：

求2¹⁰

10 = 1010 = 1*2³ + 0*2² + 1*2¹ + 0*2⁰

那么 2¹⁰ = 2¹⁰¹⁰ = 2^{1*2³ + 0*2² + 1*2¹ + 0*2⁰} = 2^1*2³ * 2^1*2¹ = 2⁸* 2²

所以只要我们对 n&1 判断它是0/1（决定是否与x的某次幂相乘），以及右移操作即可实现上述过程。

实际例子

pow(2, 5)
x = 2, res = 1;
5 & 1 -> 1 res *= x -> 2; x *= x -> 4; 5 >> 1 -> 2;  (该位为1，乘)
2 & 1 -> 0 x *= x -> 16 2 >> 1 -> 1
1 & 1 -> 1 res *= x -> 32 1 >> 1 -> 0  (该位为1，乘)
stop

pow(2, 6)
x = 2, res = 1;
6 & 1 -> 0; x *= x -> 4; 6 >> 1 -> 3;
3 & 1 -> 1; res *= x -> 4; x *= x -> 16; 2 >> 1 -> 1  (该位为1，乘)
1 & 1 -> 1; res *= x -> 64 1 >> 1 -> 0  (该位为1，乘)
stop

0101
1 : res = 1*2; 4
0 : res = 1*2； 4^2
1 : res = 1*2 * 1 * 16; 16^2

说的再直白一点，就是x一直在以x*=x，进行1 2 4 8 16次幂，而res到底要不要去乘以x的当前次幂，取决于n&1的结果（如果为1，代表要乘，0不乘），本次结束就转向前一位，即n >> 1，直到n == 0, stop.

 1 class Solution {
 2 public:
 3     double myPow(double x, int n) {
 4         double res = 1.0;
 5         if(n == 0 || x == 1.0)
 6             return 1;
 7         else if(n > 0)
 8         {
 9             while(n)
10             {
11                 if(n & 1)
12                     res *= x;
13                 x *= x;
14                 n >>= 1;
15             }
16             return res;
17         }
18         else
19         {　　//不得不用更大范围的类型，以应对INT_MIN,而且abs()不合用，可以试一下
20             unsigned int m = llabs(n);
21             while(m)
22             {
23                 if(m & 1)
24                     res *= x;
25                 x *= x;
26                 m >>= 1;
27             }
28             return 1.0/res;
29         }
30     }
31 };