0029-divide-two-integers.adoc

29. Divide Two Integers

LeetCode - 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: [-2³¹, 2³¹ - 1]. For the purpose of this problem, assume that your function returns 2³¹ - 1 when the division result overflows.

解题分析

思路其实挺简单，就是通过移位操作，把被除数不断翻倍到仅次于被除数的倍数，然后从被除数中减去这个值，剩下的部分再反复执行这个操作，直到被除数小于除数为止。

模仿这个思路 C++ bit manipulations - LeetCode Discuss 来实现的。

15 line easy understand solution. 129ms - LeetCode Discuss 这个思路也很棒。它并没有等把倍数计算到最大去减少，而是在翻倍过程中，每次都去减少；等翻倍太大，再以此"减半"。感觉效率更高！

link:{sourcedir}/_0029_DivideTwoIntegers.java[role=include]