[剑指offer]数值的整数次方
题目描述
给定一个double类型的浮点数base和int类型的整数exponent。求base的exponent次方。
解题思路
- 指数为负时,可以先对指数求绝对值,算出次方的结果后再取倒数
- 当底数为0,指数为负时,会出现对0求倒数情况,要特殊处理
- 0的0次方在数学上没有意义,因此无论输出0还是1都是可以接受的
-
在计算次方的时候,除了简单的遍历,我们可以使用递归的思想,如下公式,来减少计算量:
参考代码
public class Solution {
public double Power(double base, int exponent) {
int n = exponent;
if(exponent==0){
// 当指数为0底数为0时,没有意义,返回0或者返回1都可以
return 1;
}else if(exponent < 0){
if(base == 0){
throw new RuntimeException("分母不能为0");
}
n = -exponent;
}
double res = PowerUnsignedExponent(base, n);
return exponent<0? 1/res: res;
}
public double PowerUnsignedExponent(double base, int n){
if(n == 0)
return 1;
if(n == 1)
return base;
//递归
double res = PowerUnsignedExponent(base, n/2);
res *= res;
if(n%2 == 1)
res *= base;
return res;
}
}
代码优化
可以使用右移运算符代替除以2,用位与运算符代替求余运算符(%)来判断一个数是奇数还是偶数。
public double PowerUnsignedExponent(double base, int n){
if(n == 0)
return 1;
if(n == 1)
return base;
//递归
double res = PowerUnsignedExponent(base, n>>1);
res *= res;
if((n & 0x1) == 1)
res *= base;
return res;
}