Leetcode T29: 两数相除

题目描述

给定两个整数，被除数 dividend 和除数 divisor。将两数相除，要求不使用乘法、除法和 mod 运算符。

返回被除数 dividend 除以除数 divisor 得到的商。

整数除法的结果应当截去（truncate）其小数部分，例如：truncate(8.345) = 8 以及 truncate(-2.7335) = -2

示例 1:

输入: dividend = 10, divisor = 3
输出: 3
解释: 10/3 = truncate(3.33333…) = truncate(3) = 3

示例 2:

输入: dividend = 7, divisor = -3
输出: -2
解释: 7/-3 = truncate(-2.33333…) = -2

提示

• 被除数和除数均为 32 位有符号整数。
• 除数不为 0。
• 假设我们的环境只能存储 32 位有符号整数，其数值范围是 $[-2^{31},2^{31}-1]$。本题中，如果除法结果溢出，则返回 2^{31} − 1。

思路

由于题目中不能使用乘法、除法和取余运算，可以考虑利用加减法计算。

例如，考虑100/7=14… …2，可以使用100对7累减，直到为负数。但是，这样效率太低，可以考虑一下减去多个7（比如 $2^i$ 个7），来提高计算效率。

可以采取如下做法：
$100-2^3\ast 7=100-56=44$,
$44-2^2\ast 7=44-28=16$,
$16-2^1\ast 7=2$,

由于$2<7$，所以最后的余数是2，除数为 $2^1+2^2+2^3=14$.

但是，要考虑特殊情况：

1. 被除数为0，直接输出0.
2. 被除数为$-2^{31}$，而除数是-1，那么，根据题意，应返回$2^{31}-1$

代码

    public int divide(int dividend, int divisor) {
    
        if (dividend == 0) {
    
            return 0;
        }
        if (dividend == Integer.MIN_VALUE && divisor == -1) {
    
            return Integer.MAX_VALUE;
        }
        boolean negative;
        negative = (dividend^divisor) < 0;
        long t = Math.abs((long)dividend);
        long d = Math.abs((long)divisor);
        int result = 0;
        for(int i = 31; i >= 0; i--) {
    
        	if( (d<<i) <= t ) {
    
        		result += (1<<i);
        		t -= d<<i;
        	}
        }
        return negative ? -result : result;//符号相异取反
    }