Leetcode 50.Pow(x,n) 使用快速幂求解
快速幂介绍
基础前提
1.任何数都可以用二进制表示
2.
x
n
1
+
n
2
+
n
3
=
=
x
n
1
∗
x
n
2
∗
x
n
3
x^{n_1+n_2+n_3}==x^{n_1} * x^{n_2} * x^{n_3}
xn1+n2+n3==xn1∗xn2∗xn3
由此基本前提可推论得
接下来举Pow(2,11)的例子说明
1
1
10
=
=
101
1
2
11_{10} == 1011_2
1110==10112
因此，原式可以写成
P
o
w
(
2
,
11
)
=
=
2
8
∗
2
2
∗
2
1
Pow(2,11) == 2^{8} * 2^{2} * 2^{1}
Pow(2,11)==28∗22∗21
因此，只需要把原式中的指数n先化为2进制，再转化为乘法的形式即可
而每次乘的因子来自于
2
2
2的每次平方
即
2
8
=
=
2
4
∗
2
=
=
2
2
∗
2
∗
2
2^8 == 2^{4*2} == 2^{2*2*2}
28==24∗2==22∗2∗2
所以只需要存储一个临时temp变量，用来计算每次平方的值；如果这一位二进制是1，就乘上；否则就不管。
下面附上代码
class Solution {
public:
double myPow(double x, int n) {
string a = "";
long double k;
int flag = 0;
if(n < 0)
{
k = 1/x;
}
else k = x;
x=1;
while(n)
{
a += (char)(n%2+'0');
n/=2;
}
while(a != "")
{
int temp = a[0]-'0';
if(temp)x *= k;
a = a.substr(1);
k *= k;
}
return x;
}
};