题目地址

两数相除
难度 中

思路

总体思路相似，通过循环减除数的方式来找到最后的商。区别在于递减使用加减法还是位运算

思路1

常规的加法处理

public int divide(int dividend, int divisor) {
        if(dividend == 0) return 0;
        boolean positive = false;
        // 注意边界值溢出情况的处理，主要是负数边界值和正数边界值
        if(dividend == Integer.MIN_VALUE && divisor == -1) return Integer.MAX_VALUE;
        if(divisor == -1) return -1*dividend; 
        if (divisor == 1) return dividend;
        // 获取结果符号
        if ((dividend > 0 && divisor > 0 ) || (dividend < 0 && divisor < 0)) positive = true; 
        if (dividend > 0) dividend *= -1;
        if (divisor > 0) divisor *= -1;

        int rs = div(dividend, divisor);
        return positive ? rs : rs * -1;
    }

    /**
    统一作为负数进行处理；迫近边界
    */
    int div(int dividend, int divisor) {
        int rs = 0;
        while(dividend <= divisor) {
            rs ++;
            dividend -= divisor;
        }
        return rs;
    }

思路2

使用位运算进行叠加，但是不用一位一位去算，而是根据位移运算进行快速递增运算（指数级别递增），减少大量循环运算

public int divide(int dividend, int divisor) {
        if(dividend == 0) return 0;
        if(dividend == Integer.MIN_VALUE && divisor == -1) return Integer.MAX_VALUE;
        if(divisor == 1) return dividend;

        boolean positive = false;
        // 设置正负值
        if ((dividend > 0 && divisor > 0 ) || (dividend < 0 && divisor < 0)) positive = true; 
        // 全部处理为正数，并且防止溢出
        long dividend1 = Math.abs((long)dividend);
        long divisor1 = Math.abs((long)divisor);

        int rs = div(dividend1, divisor1);
        return positive ? rs : rs * -1;
    }

    /**
    统一作为正数进行处理；迫近边界
    */
    int div(long dividend, long divisor) {
        int rs = 0;
        // 设置被除数作为递减，multi作为商
        while(dividend >= divisor) {
            // 每次都将除数倍增至最大。商的概念就是有多少个除数
            // 所以当除数*2，商也*2；用位运算表示就是 << 1
            // 每次迭代最新的被除数，迭代至被除数 < 除数
            long temp = divisor, multi = 1;
            // 判断当前循环的临界点，被除数是否能大于等于2倍，可以的使用位运算快速递增；不能的话使用+1进行计算 
            while(dividend >= (temp << 1)) {
                temp <<= 1;
                multi <<= 1;
            }
            dividend -= temp;
            // 获取增加的商，位运算不参与的话默认+1这样递增；
            rs += multi;
        }
        return rs;
    }

Q.E.D.