数值的整数次方.md

题目描述

实现函数double power(double base, int exponent)，求base的exponent次方。不得使用库函数，同时不需要考虑大数问题。

测试用例

把 底数 和 指数 分别设为正数、负数和零。

题目考点

• 考察应聘者 思维的全面性。
• 对效率比较高的面试官还会考察应聘者快速做乘方的能力。

解题思路

全面但不够高效的解法

考虑exponent为负数

当指数为负数的时候，我们可以先对指数取绝对值，算出次方的结果之后再取倒数。在想到取倒数的时候，我们又要想到对0取倒数的问题，这就要我们进行错误处理，处理的方式主要有三种：返回值、全局变量和异常。面试的时候可以阐述每种方法的优缺点，然后一起讨论决定选用哪种方法。

值得注意的是，由于0的0次方在数学上是没有意义，因此无论输出是0还是1都可以接受，但这都需要和面试官说清楚，表明我们已经考虑到这个边界值了。

既全面又高效的解法

这是对上面解法的补充，主要利用了下面的公式：

a^n = a^(n/2) * a^(n/2) ; n为偶数
a^n = a^((n-1)/2) * a^((n-1)/2) * a ; n为鸡数

自己解题

/**
 * 数值的整数次方
 *
 * @Author rex
 * 2018/7/21
 */
public class Solution {
    /**
     * 自己解题
     *
     * @param base
     * @param exponent
     * @return
     */
    public double power(double base, int exponent) {
        double result = 1.0;
        for (int i = 1; i <= exponent; i++) {
            result *= base;
        }
        return result;
    }
}

考虑欠缺点：

只考虑base的正负号，还以为这么简单，却没有考虑exponent的正负号。

参考解题

全面但不够高效的解法

import java.math.BigDecimal;

/**
 * 数值的整数次方
 *
 * @Author rex
 * 2018/7/21
 */
public class Solution1 {

    private boolean g_invalid_input = false;

    /**
     * 全面但不够高效的解法
     *
     * @param base
     * @param exponent
     * @return
     */
    public double power(double base, int exponent) {
        // 0的0次方没有意义
        if (doubleCompare(base, 0.0) == 0 && exponent == 0) {
            g_invalid_input = false;
            return 0.0;
        }
        int absExponent = Math.abs(exponent);
        double result = powerWithPositiveExponent(base, absExponent);
        if (exponent < 0) {
            result = 1.0/result;
        }
        return result;
    }



    /**
     * 指数为正时，得到的整数次方
     *
     * @param base
     * @param exponent
     * @return
     */
    public double powerWithPositiveExponent(double base, int exponent) {
        double result = 1.0;
        for (int i = 1; i <= exponent; i++) {
            result *= base;
        }
        return result;
    }

    /**
     * 比较两个浮点型大小
     * @param a
     * @param b
     * @return
     */
    public int doubleCompare(double a, double b) {
        BigDecimal data1 = new BigDecimal(a);
        BigDecimal data2 = new BigDecimal(b);
        return data1.compareTo(data2);
    }
}

既全面又高效的解法

import java.math.BigDecimal;

/**
 * 数值的整数次方
 *
 * @Author rex
 * 2018/7/21
 */
public class Solution2 {

    private boolean g_invalid_input = false;

    /**
     * 全面但不够高效的解法
     *
     * @param base
     * @param exponent
     * @return
     */
    public double power(double base, int exponent) {
        // 0的0次方没有意义
        if (doubleCompare(base, 0.0) == 0 && exponent == 0) {
            g_invalid_input = false;
            return 0.0;
        }
        int absExponent = Math.abs(exponent);
        double result = powerWithPositiveExponent(base, absExponent);
        if (exponent < 0) {
            result = 1.0/result;
        }
        return result;
    }



    /**
     * 指数为正时，得到的整数次方
     *
     * @param base
     * @param exponent
     * @return
     */
    public double powerWithPositiveExponent(double base, int exponent) {
        if (exponent == 0) {
            return 1;
        }
        if (exponent == 1) {
            return base;
        }
        double result = powerWithPositiveExponent(base, exponent >> 1);
        result *= result;
        // 对2取余，判断奇偶数
        if ((exponent & 0x1) == 1) {
            result *= base;
        }
        return result;
    }

    /**
     * 比较两个浮点型大小
     * @param a
     * @param b
     * @return
     */
    public int doubleCompare(double a, double b) {
        BigDecimal data1 = new BigDecimal(a);
        BigDecimal data2 = new BigDecimal(b);
        return data1.compareTo(data2);
    }
}

补充

返回值、全局变量和异常处理3种错误处理方式的优缺点比较

	优点	缺点
返回值	和系统API一致	不能方便得使用计算结果
全局变量	能够方便使用计算结果	用户可能会忘记检查全局变量
异常	可以为不用的出错原因定义不同的异常类型，逻辑清晰明了	有些语言不支持，抛出异常时对性能有负面影响

以后需要用右移运算符代替除以2，用位与运算符代替求余运算符来判断一个数是奇数还是偶数。