题目大意：
两数相除
给定两个整数，被除数 dividend 和除数 divisor。将两数相除，要求不使用乘法、除法和 mod 运算符。
返回被除数 dividend 除以除数 divisor 得到的商。
示例 1:
输入: dividend = 10, divisor = 3 输出: 3
示例 2:
输入: dividend = 7, divisor = -3 输出: -2
说明:
- 被除数和除数均为 32 位有符号整数。
- 除数不为 0。
- 假设我们的环境只能存储 32 位有符号整数，其数值范围是 [−231, 231 − 1]。本题中，如果除法结果溢出，则返回 231 − 1。
如果想查看本题目是哪家公司的面试题，请参考以下免费链接： https://leetcode.jp/problemdetail.php?id=29
解题思路分析：
本题要考虑除法的本质，比如a/b，代表了a中包含有多少个b，最笨的方法可以使用a不停的减去b，直到a小于b为止，减法操作的次数即是结果。但是这样做效率很低，比如1亿除以1，我们要循环1亿次，显然执行时会超时。接下来我们考虑一种比较高效的方式。
举个例子，比如计算101除以5，也就是101中包含多少个5，首先101大于5，所以101中至少包含1个5，然后，我们可以将5乘以2，再看101是否大于等于10，以此类推：
101, 5 // 101大于等于5，因此101中至少包含1个5，将5乘以2 101, 10 // 101大于等于10，因此101中至少包含1个10，将10乘以2 101, 20 // 101大于等于20，因此101中至少包含1个20，将20乘以2 101, 40 // 101大于等于40，因此101中至少包含1个40，将40乘以2 101, 80 // 101大于等于80，因此101中至少包含1个80，将80乘以2 101, 160 // 101小于160，退出循环
通过以上的推导，我们知道101中包含一个80，从5变到80，我们乘了16次，因此，101中至少包含了16个5。但这时还没有结束，101与80之间还相差了21，因此我们还需要再看21中包含多少个5才行，同理，按照上述的步骤可得出，21中还包含了4个5，因此，总共101中包含有20个5。
此外还需要注意一点，题目要求不能使用乘法，上面的乘2操作我们需要使用位运算<<来代替。
10 * 2 == 10 << 1
最后还要吐槽一下本题的test case，解题时要考虑到Integer.MAX_VALUE与Integer.MIN_VALUE之间转化会出现int越界。比如 MIN_VALUE / -1。
实现代码：
public int divide(int dividend, int divisor) {
// 最终结果是否为正数
boolean mark=dividend>0&&divisor>0||dividend<0&&divisor<0;
// 将除数与被除数转化为long型正数
long dividendL=Math.abs((long)dividend);
long divisorL=Math.abs((long)divisor);
long res=0; // 返回结果
// 当被除数大于等于除数时
while(dividendL>=divisorL){
// 除数
long d = divisorL;
// 被除数中包含除数的个数
// 因为当前被除数大于等于除数，因此至少包含1个
long count=1;
// 当被除数大于等于2倍的除数时
while(dividendL>=(d<<1)){
// 除数乘以2
d=(d<<1);
// 被除数中包含除数的个数乘以2
count=(count<<1);
}
// 将包含个数累加到返回结果
res+=count;
// 被除数减去除数
dividendL-=d;
}
// 如果返回结果大于int最大值
if(res>Integer.MAX_VALUE){
// 如果结果是正数，返回int最大值，反之返回int最小值
return mark?Integer.MAX_VALUE:Integer.MIN_VALUE;
}
return mark ? (int)res:(int)-res;
} 本题解法执行时间为1ms。
Runtime: 1 ms, faster than 100.00% of Java online submissions for Divide Two Integers.
Memory Usage: 39.1 MB, less than 6.06% of Java online submissions for Divide Two Integers.
本网站文章均为原创内容，并可随意转载，但请标明本文链接如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: http://leetcode.jp/leetcode-29-divide-two-integers-解题思路分析/
View Comments (0)