给定一个double类型的浮点数base和int类型的整数exponent。求base的exponent次方。
第一种
根据幂的定义来计算。
public double Power(double base, int exponent) {
int absExp = Math.abs(exponent);
double result = 1.0;
for (int i = 0; i < absExp; i++) {
result *= base;
}
if (exponent < 0) {
result = 1 / result;
}
return result;
}
以上程序可以通过牛客的测试用例,不过没有对base exponent的范围进行开考虑和限制。
第二种
考虑2^5,相当于 (2^2) * (2^2) * 2,也就是我们将exponent使用折半计算在相乘的技巧减少计算的次数。下面先用递归实现这种技巧。
public double Power(double base, int exponent) {
if (isZero(base)) { //判断base是否是特殊值
return 0.0;
}
if (exponent == 1) {
return base;
} else if (exponent == 0) {
return 1.0;
}
int absExp = Math.abs(exponent);
double result = 0.0;
result = compute(base, absExp);
if (exponent < 0) {
result = 1 / result;
}
return result;
}
private double compute(double base, int exp) {
if (exp == 1) {
return base;
} else if (exp == 0) {
return 1.0;
}
//使用移位操作来代替除法操作 这样更加高效
double result = compute(base, exp >> 1);
result *= result;
// 同样使用位运算来代替求余操作
if ((exp & 0x1) == 1) {
result *= base;
}
return result;
}
private boolean isZero(double base) {
// 不要对double值使用==判断是否是0
if (Math.abs(base - 0) < 0.0000000001) {
return true;
}
return false;
}
以上代码需要注意的首先是对base exponent值进行了考虑和限制,其次是递归的使用,最后使用了位运算来代替除法和求余操作,提高了效率。
第三种
这里使用迭代来实现上面的计算技巧。
public double Power(double base, int exponent) {
if (isZero(base)) {
return 0.0;
}
if (exponent == 1) {
return base;
} else if (exponent == 0) {
return 1.0;
}
int absExp = Math.abs(exponent);
double result = base;
boolean isOdd = ((absExp & 1) == 1);
if (isOdd) {
absExp = absExp - 1;
}
absExp = absExp >> 1;
while (absExp != 0) {
result *= result;
absExp = absExp >> 1;
}
if (isOdd) {
result *= base;
}
if (exponent < 0) {
result = 1 / result;
}
Math.pow(base, 10.0);
return result;
}
private boolean isZero(double base) {
if (Math.abs(base - 0) < 0.0000000001) {
return true;
}
return false;
}
网友评论