leetCode29. 两数相除

题目描述

/**
     * 给定两个整数，被除数 dividend 和除数 divisor。
     * 将两数相除，要求不使用乘法、除法和 mod 运算符。
     * <p>
     * 返回被除数 dividend 除以除数 divisor 得到的商。
     * <p>
     * 整数除法的结果应当截去（truncate）其小数部分，例如：truncate(8.345) = 8
     * 以及 truncate(-2.7335) = -2
     */

思路分析

1. 两数相除，不能使用乘法 除法和取模运算，因此只能使用加减法
2. 先比较除数和被除数的大小，如果除数大于被除数，则结果为零
3. 否则定义一个变量保存相除的结果，默认为1，然后将除数 * 2 再和被除数比较，如果被除数仍然大，则结果 * 2，除数乘以2，再比较，使用循环，直到除数 * 2后大于被除数为止
4. 当上述条件不满足后，使用递归计算被除数中剩下的值中包含有几个除数,将其累加到结果中
5. 在实际计算中要注意计算结果越界的情况
6. 源码见下

源码及分析

 /**
     *
     * @param dividend 被除数
     * @param divisor 除数
     * @return 相除的结果
     */
    public int divide(int dividend, int divisor) {
        //分子为0的情况
        if (dividend == 0) return 0;
        //分母为1的情况
        if (divisor == 1) return dividend > Integer.MAX_VALUE ? Integer.MAX_VALUE : dividend;
        //分母为-1的情况
        if (divisor == -1) return dividend < -Integer.MAX_VALUE ? Integer.MAX_VALUE : -dividend;
        //定义两个变量保存除数和被除数
        long a = dividend, b = divisor;
        //定义两数相处的符号位
        int sign = 1;
        //判断相除的结果的正负
        if ((a > 0 && b < 0) || (a < 0 && b > 0)) {
            sign = -1;
        }
        //若两数为负数，将其置为正数
        a = a > 0 ? a : -a;
        b = b > 0 ? b : -b;
        //计算
        int res = div(a, b);
        //根据符号位返回相应的结果，注意不能溢出
        if (sign > 0){
            return res > Integer.MAX_VALUE ? Integer.MAX_VALUE : res;
        }
        return -res;
    }

    /**
     * 实现两个长整型数相处，不考虑溢出
     *
     * @param x 被除数
     * @param y 除数
     * @return 计算的结果
     */
    public int div(long x, long y) {
        //如果被除数小于除数
        if (x < y) {
            return 0;
        }
        //定义变量保存除法的结果
        int count = 1;
        //定义变量保存除数的值，因为除数不能变，递归时还要使用
        long tmp = y;
        //循环结束时tmp < x < tmp * 2
        while (x >= tmp * 2) {
            count = count * 2;
            tmp = tmp * 2;
        }
        //递归计算
        return count + div(x - tmp, y);
    }

leetCode29. 两数相除