【剑指offer-Java版】11数值的整数次方

我不是女神ヾ 2022-08-21 08:57 86阅读 0赞

不用库，实现pow()运算  
很简单的题目，但是涉及到很多细节

比如  
1) 结果非法或者出错的时候如何通知调用者:  
可以采用返回特定值的方法-但是此处pow运算既可以返回正数 0 或者负数，所以此思路比较麻烦  
可以采用全局变量加上返回值的方法-缺点是比较容易忘记检查全局变量的标志  
可以直接使用异常机制来实现-就是此处的方法了，虽然异常的缺点在于可能会导致程序执行流程的极大改变，但是比较方便

2) 输入的组合情况  
base为正 exp为正 - 直接算  
base为负 exp为正 - 直接计算  
base为0 exp为正 直接返回0

base为正 exp为0 - 直接返回1  
base为负 exp为0 - 直接返回1  
base为0 exp为0 - 无意义，返回1

base为正 exp为负 - 正常计算后求倒  
base为负 exp为负 - 正常计算求倒  
base为0 exp为负 - 非法运算抛出异常

3) 其他的一些优化以及注意的细节  
pow运算针对的都是浮点运算，所以精度有要求-浮点数大小对比需要不是和0而是和0.00…..0001  
一些计算加速技巧-需要积累

public class _Q11 {
    
        public double Pow(double base, int exp) throws Exception{
    
            if(equals(base, 0.0) && (exp < 0)) { throw new Exception("invalid input, check the base");}
    
            if(equals(base, 0)) return 0;
    
            if(exp == 0) return 1;
    
            if(exp == 1) return base;
    
            if(exp < 0) return 1.0/PowWithUnsignedExpR(base, -exp);
    
            return PowWithUnsignedExp(base, exp);
        }
    
        /**
         * 这个地方看到书上是用的递归，代码挺巧妙的就是不易读 - 需要结合那个公式
         */
        public double PowWithUnsignedExp(double base, int exp){
            double result = base;
            int count = 1;
    
            if((exp & 0x01) == 0){ // 指数为偶数
                while(count < exp){
                    result = result*result;
                    count = (count<<1);
                }
            }else{ // 指数为奇数
                while(count < (exp - 1)){
                    result = result*result;
                    count = (count<<1);
                }
                result = result * base;
            }
    
            return result;
        }
    
        public double PowWithUnsignedExpR(double base, int exp){
            // 出口
            if(exp <= 1) return exp*base;
    
            double result = PowWithUnsignedExpR(base, exp>>1);
    
            result *= result;
    
            if((exp & 0x01) == 1) result *= base; 
    
            return result;
        }
    
        public boolean equals(double num1, double num2){
            boolean result = false;
            if((num1 - num2 < 0.00001) && (num1 - num2 > -0.00001)) result = true;
            return result;
        }
        }

测试代码：

public class _Q11Test extends TestCase {
        
    
        _Q11 pow = new _Q11();
    
        public void testMinInReverse() throws Exception{
            double base1 = 0.0;
            int exp1 = 2;
    
            double base2 = 0.0;
            int exp2 = -2;
    
            double base3 = 5;
            int exp3 = 1;
    
            double base4 = 5;
            int exp4 = -2;
    
            double base5 = 5;
            int exp5 = 0;
    
            double base6 = 5;
            int exp6 = 2;
    
            System.out.println(pow.Pow(base1, exp1));
            try {
                System.out.println(pow.Pow(base2, exp2));
            } catch (Exception e) {
                e.printStackTrace();
            }
            System.out.println(pow.Pow(base3, exp3));
            System.out.println(pow.Pow(base4, exp4));
            System.out.println(pow.Pow(base5, exp5));
            System.out.println(pow.Pow(base6, exp6));
        }
        }