数值的整数次方

作者: lvlvforever | 来源:发表于2018-07-17 14:11 被阅读6次

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

    相关文章

      网友评论

        本文标题:数值的整数次方

        本文链接:https://www.haomeiwen.com/subject/bfgwpftx.html