当前位置: 编程技术>java/j2ee
一种求正整数幂的高效算法详解
来源: 互联网 发布时间:2014-10-26
本文导语: 核心思想是当n为偶数时,a^n = a^n/2 × a^n/2当n为奇数时,a^n = a^(n-1)/2 × a^(n-1)/2 × a代码如下: 代码如下:public class Power { public static void main(String[] args) { System.out.println(power(5.5,5)); } private static double power(double base, int exponent) {...
核心思想是
当n为偶数时,a^n = a^n/2 × a^n/2
当n为奇数时,a^n = a^(n-1)/2 × a^(n-1)/2 × a
代码如下:
public class Power {
public static void main(String[] args) {
System.out.println(power(5.5,5));
}
private static double power(double base, int exponent) {
if (exponent == 0)
return 1;
if (exponent == 1)
return base;
double result = power(base, exponent >> 1);
result *= result;
if ((exponent & 0x1) == 1)
result *= base;
return result;
}
}
代码中还使用右移运算来代替除以2,用位与运算来代替求余判断奇偶,这样都要算法更加效率的多。
当n为偶数时,a^n = a^n/2 × a^n/2
当n为奇数时,a^n = a^(n-1)/2 × a^(n-1)/2 × a
代码如下:
代码如下:
public class Power {
public static void main(String[] args) {
System.out.println(power(5.5,5));
}
private static double power(double base, int exponent) {
if (exponent == 0)
return 1;
if (exponent == 1)
return base;
double result = power(base, exponent >> 1);
result *= result;
if ((exponent & 0x1) == 1)
result *= base;
return result;
}
}
代码中还使用右移运算来代替除以2,用位与运算来代替求余判断奇偶,这样都要算法更加效率的多。