文章目录
1. 题目
2. 思路
(1) 模拟法
(2) 快速幂
- 当求x的n次方时,若n为偶数,则x的n次方等于两个x的n/2次方相乘;若n为奇数,则x的n次方等于两个x的(n-1)/2次方相乘再乘以x。如x的16次方等于x的8次方乘以x的8次方,x的15次方等于x的7次方乘以x的7次方乘以x。
- 利用右移运算代替除以2,利用与运算代替判断奇偶性,利用递归实现快速幂。
3. 代码
public class Test {
public static void main(String[] args) {
}
}
class Solution {
public double myPow(double x, int n) {
if (x == 1 || n == 0) {
return 1;
}
if (x == -1) {
return (n & 1) == 0 ? 1 : -1;
}
long nl = n;
if (n < 0) {
x = 1 / x;
nl = -nl;
}
double res = 1.0;
while (nl > 0) {
res = res * x;
if (res == 0) {
return 0;
}
nl--;
}
return res;
}
}
class Solution1 {
public double myPow(double x, int n) {
if (x == 0) {
return 0;
}
long nl = n;
if (n < 0) {
x = 1 / x;
nl = -nl;
}
return myPow(x, nl);
}
private double myPow(double x, long n) {
if (n == 0) {
return 1;
}
if (n == 1) {
return x;
}
double pre = myPow(x, n >> 1);
pre *= pre;
if ((n & 1) == 1) {
pre *= x;
}
return pre;
}
}