剑指Offer题解

数值的整数次方

2018-07-17  本文已影响6人  lvlvforever

给定一个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;
    }

上一篇 下一篇

猜你喜欢

热点阅读