友情支持
如果您觉得这个笔记对您有所帮助，看在D瓜哥码这么多字的辛苦上，请友情支持一下，D瓜哥感激不尽，😜
|
|
有些打赏的朋友希望可以加个好友，欢迎关注D 瓜哥的微信公众号，这样就可以通过公众号的回复直接给我发信息。
公众号的微信号是: jikerizhi。因为众所周知的原因，有时图片加载不出来。 如果图片加载不出来可以直接通过搜索微信号来查找我的公众号。 |
29. Divide Two Integers
Given two integers dividend and divisor, divide two integers without using multiplication, division and mod operator.
Return the quotient after dividing dividend by divisor.
The integer division should truncate toward zero.
Example 1:
Input: dividend = 10, divisor = 3 Output: 3
Example 2:
Input: dividend = 7, divisor = -3 Output: -2
Note:
-
Both dividend and divisor will be 32-bit signed integers.
-
The divisor will never be 0.
-
Assume we are dealing with an environment which could only store integers within the 32-bit signed integer range: [-231, 231 - 1]. For the purpose of this problem, assume that your function returns 231 - 1 when the division result overflows.
解题分析
思路其实挺简单，就是通过移位操作，把被除数不断翻倍到仅次于被除数的倍数，然后从被除数中减去这个值，剩下的部分再反复执行这个操作，直到被除数小于除数为止。
模仿这个思路 C++ bit manipulations - LeetCode Discuss 来实现的。
15 line easy understand solution. 129ms - LeetCode Discuss 这个思路也很棒。它并没有等把倍数计算到最大去减少，而是在翻倍过程中，每次都去减少；等翻倍太大，再以此"减半"。感觉效率更高！
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
/**
* Runtime: 1 ms, faster than 100.00% of Java online submissions for Divide Two Integers.
*
* Memory Usage: 34.3 MB, less than 6.06% of Java online submissions for Divide Two Integers.
*
* Copy from: https://leetcode.com/problems/divide-two-integers/discuss/13407/C%2B%2B-bit-manipulations[C++ bit manipulations - LeetCode Discuss]
*/
public int divide(int dividend, int divisor) {
if (dividend == Integer.MIN_VALUE && divisor == -1) {
return Integer.MAX_VALUE;
}
int sign = dividend > 0 ^ divisor > 0 ? -1 : 1;
long ldividend = Math.abs((long) dividend);
long ldivisor = Math.abs((long) divisor);
int result = 0;
while (ldividend >= ldivisor) {
long temp = ldivisor;
int mul = 1;
while (temp << 1 <= ldividend) {
temp <<= 1;
mul <<= 1;
}
ldividend -= temp;
result += mul;
}
return result * sign;
}