原文链接 http://blog.csdn.net/qq_22329521/article/details/52979194
实现函数 double Power(double base,int exponent),求base的exponent的次。不考虑大数问题
自以为题目简单的解法（错误案例)
//error
double power(double base, int exponent) {
double result=1.0;
for (int i=1;i<exponent;i++){
result*=base;
}
return result;
}
不考虑任何边界情况，如果输入指数是小于1即0和负数的时候
修改代码后
//判断是否输出参数有误
static boolean g_invalidInput = false;
public static double power(double base, int exponent) {
g_invalidInput = false;
if (equal(base, 0.0) **exponent< 0){
g_invalidInput = true;
return 0;
}
int abExponent;
if (exponent < 0) {
abExponent = -exponent;
}
double result = PowerWithUnsigindExponent(base, abExponent);
//如果指数是负的在这里做倒数
if (exponent < 0) {
result = 1 / result;
}
return result;
}
double PowerWithUnsigindExponent(double base, int exponent) {
double result = 1.0;
for (int i = 1; i < exponent; i++) {
result *= base;
}
return result;
}
boolean equal(double num1, double num2) {
if ((num1 - num2) > -0.0000001 && (num1 - num2) < 0.0000001) {
return true;
} else return false;
}
在计算机表示小数都有误差，不能用等于判断两个小数是否相等，如果两个小数的差小于多少，我们认为他们相等
全面高效的解法
--
如果我们输入的指数是32，我们在循环中需要做31此乘法，单是问你可以在16此乘法中，在平方一次就可以了，而16此平方，只要在8的平方上就可以了， 我们可以用以下公式处理
这里写图片描述
我们在PowerWithUnsigindExponent修改 可以在达到O(logn) 的时间复杂度
public static double PowerWithUnsigindExponent(double base,int exponent){
if(exponent ==0 ){
return 1;
}
if(exponent == 1){
return base;
}
if(exponent>>1==0){
int exponent1 = exponent>>1;
double result = power(base,exponent1);
return result*result;
}else{
int exponent2 = exponent-1;
double result = power(base,exponent2);
return result*base;
}
}
我们用位运算符替代%求余来判断是否奇数还是偶数，位运算的效率比乘除法的效率要高很多。
