【快速幂】剑指 Offer 16. 数值的整数次方
题目描述
实现 pow(x, n) ，即计算 x 的 n 次幂函数（即， x n x^n xn）。不得使用库函数，同时不需要考虑大数问题。
提示：
−
100.0
<
x
<
100.0
-100.0 < x < 100.0
−100.0<x<100.0
−
2
31
<
=
n
<
=
2
31
−
1
-2^{31} <= n <= 2^{31}-1
−231<=n<=231−1
−
1
0
4
<
=
x
n
<
=
1
0
4
-10^4 <= x^n <= 10^4
−104<=xn<=104
快速幂思想
对于 x n x^n xn可以视为 x n = x n / 2 ∗ x n / 2 x^n=x^{n/2}*x^{n/2} xn=xn/2∗xn/2
- 当 n / 2 {n/2} n/2为偶数时， x n = ( x n / / 2 ) 2 x^{n}=(x^{n//2})^2 xn=(xn//2)2
- 当 n / 2 {n/2} n/2为奇数时， x n = ( x n / / 2 ) 2 ∗ x x^{n}=(x^{n//2})^2*x xn=(xn//2)2∗x
其中 n / / 2 n//2 n//2表示 n n n整除 2 2 2的结果
所以，我们可以设置一个变量res=1；初始状态
x
n
=
x
n
∗
r
e
s
x^{n}=x^n*res
xn=xn∗res，每一次循环，令
x
=
x
∗
x
x=x*x
x=x∗x，即
n
=
n
/
2
∗
2
n=n/2*2
n=n/2∗2文章来源：https://www.toymoban.com/news/detail-430893.html
- 当 n / 2 {n/2} n/2为偶数时， r e s = r e s ; x ∗ = x ; n / = 2 res=res;x*=x;n/=2 res=res;x∗=x;n/=2
- 当 n / 2 {n/2} n/2为奇数时， r e s = r e s ∗ x ; x ∗ = x ; n / = 2 res=res*x;x*=x;n/=2 res=res∗x;x∗=x;n/=2
当且仅当 n = 0 n=0 n=0时，退出循环。文章来源地址https://www.toymoban.com/news/detail-430893.html
题解
class Solution
{
public:
double myPow(double x, int n)
{
long m=n;
if (x == 0)
{
return 0;
}
if(1==x)
{
return x;
}
double res = 1;
if (m < 0)
{
m = -m;
x = 1 / x;
}
while (m)
{
if(m&1)
{
res*=x;
}
x*=x;
m>>=1;
}
return res;
}
};
到了这里，关于【快速幂】剑指 Offer 16. 数值的整数次方的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
