题目描述:

给定两个整数,被除数 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。

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/divide-two-integers
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

解题思路:

看到这个题目首先想到的是暴力解除法,也就是用最简单的方法:先判断出来最后的商的正负,然后取除数和被除数的绝对值操作,如果被除数的绝对值减去除数的绝对值,把结果赋给新的被除数,如果新的被除数大于零,就计数count加一,不断重复,直到新的被除数小于零,则返回计算的结果。
这种发实现很简单,但是当被除数的绝对值很大,除数的绝对值很小的时候,重复操作的次数就会很多,会造成运行的时间过长,果然在LeetCode的系统里面是不允许的。所以要另辟他径。
有这样一条思路,为了简单说明,先假设dividend和divisor都是整数,事实上在算法开始的时候第一步就会判断结果的正负,然后取dividend和divisor进行操作,这里以13除以3为例:
1、如果dividend大于等于divisor就设定,count=1;
2、如果dividend大于等于(divisor+divisor),temp_divisor=divisor+divisor,count=count+count;
3、重复第2步,直到dividend小于(divisor+divisor)就跳出循环,记录下这是的count,dividend = dividend-temp_divisor,再回到第1步重复,最后把所有的所有记录下来的count都加起来,加上预先判断好的正负号,就得到最后的结果。

代码(Java):

public class doingmyself {
	public static void main(String[] args) {
		int dividend = -2147483648;
		int divisor = 3;
		System.out.println(divide(dividend, divisor));
	}
	public static int divide(int dividend, int divisor) {
		boolean flag = true;
		if((dividend>0 && divisor<0) || (dividend<0 && divisor>0)) flag = false;
		if(dividend == 0) return 0;
		if(divisor == 1) return dividend;
		if(divisor == -1) {
			if(dividend != Integer.MIN_VALUE) return -dividend;
			return Integer.MAX_VALUE;
		}
		double absdividend = Math.abs((double)dividend);
		double absdivisor = Math.abs((double)divisor);
		double ans = 0;
		ans = div(absdividend,absdivisor);
		if(flag == false) ans = -ans;
//		System.out.println("ans = "+ans);
		return (int)ans;
	}
	
	public static double div(double dividend, double divisor) {
		if(dividend<divisor) return 0;
		int count = 1;
		double temp_divisor = divisor;
		while(dividend >= temp_divisor+temp_divisor) {
			temp_divisor = temp_divisor+temp_divisor;
			count = count+count;
		}
		return count + div(dividend-temp_divisor,divisor);
	}
}