参考资料：左程云算法课 ， 《程序员代码面试指南》
50. Pow(x, n)
Implement pow(x, n), which calculates x raised to the power n (i.e., xn).
Example 1:
Input: x = 2.00000, n = 10
Output: 1024.00000
Example 2:
Input: x = 2.10000, n = 3
Output: 9.26100
思路：
以求
1
0
75
10^{75}
1075为例，
75
=
64
+
8
+
2
+
1
=
(
1001011
)
2
75 = 64+8+2+1=(1001011)_2
75=64+8+2+1=(1001011)2
so,
1
0
75
=
1
0
64
×
1
⋅
1
0
32
×
0
⋅
1
0
16
×
0
⋅
1
0
8
×
1
⋅
1
0
4
×
0
⋅
1
0
2
×
1
⋅
1
0
1
×
1
=
1
0
(
1001011
)
2
10^{75}=10^{64\times1}·10^{32\times0}·10^{16\times0}·10^{8\times1}·10^{4\times0}·10^{2\times1}·10^{1\times1}=10^{ (1001011)_2}
1075=1064×1⋅1032×0⋅1016×0⋅108×1⋅104×0⋅102×1⋅101×1=10(1001011)2
we assume that base=10, res=1.
二进制表示的最低位(最右边的那一位)是1， 那么
r
e
s
=
r
e
s
×
b
a
s
e
=
10
,
b
a
s
e
=
b
a
s
e
×
b
a
s
e
=
1
0
2
res = res \times base = 10, base = base\times base=10^2
res=res×base=10,base=base×base=102
二进制表示的倒数第二位是0，那么
r
e
s
=
r
e
s
=
10
,
b
a
s
e
=
b
a
s
e
×
b
a
s
e
=
1
0
4
res = res = 10, base = base\times base=10^4
res=res=10,base=base×base=104
and so on. we can get the ans, which is the final 'res`.文章来源：https://www.toymoban.com/news/detail-480056.html
注：整数的幂可以扩展到矩阵的幂， 把res的起点设置为单位矩阵即可。矩阵幂的应用见斐波那契数列相关问题（详细可查阅《程序员代码面试指南》）。
注2： 这道题要考虑到幂可能取负数。对于普通负数，我们也可以直接取相反数，计算得结果后再取倒数即可；特别要注意的是，幂可能取到 系统最小值， 这时直接取相反数还是 系统最小指 它自身，于是需要特别处理，大致思路是
x
M
I
N
=
x
M
I
N
+
1
/
x
x^{MIN} = x^{MIN+1}/x
xMIN=xMIN+1/x，而
x
M
I
N
+
1
x^{MIN+1}
xMIN+1是一种普通情况可以调用当前这个函数解决。
详细见代码。文章来源地址https://www.toymoban.com/news/detail-480056.html
public double myPow(double x, int n){
if(x==0||x==1){return x;}
if(n==0){return 1;}
// there exists one case "x=2.00000, n=-2147483648"
if(n==Integer.MIN_VALUE)
{
if(x>1 || x<-1){return 0;}
return myPow(x,n+1)/x;
}
boolean isPos = true;
if(n<0)
{
isPos=false;
n =-n;
}
double base=x;
double res = 1;
for(;n!=0;n>>=1)
{
if((n&1)==1)
{
res*=base;
}
base = base*base;
}
return isPos?res:1/res;
}
到了这里，关于LeetCode ! 50. Pow(x, n)的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
