Bit Manipulation Counting and shifting bits
120. Divide Two Integers
You are given two signed 32-bit integers, dividend and divisor. Return dividend divided by divisor,
with the fraction cut off. Cutting off the fraction moves the answer toward zero: 7 divided by 2 is 3.5, so
the answer is 3, and −7 divided by 2 is −3.5, so the answer is −3.
The answer must fit in a signed 32-bit integer, from −231 to 231 − 1. Only one division goes outside that range: −231 divided by −1 is 231. For that one, return 231 − 1.
Interviewers ask for this without the multiplication, division and remainder operators (*, / and %),
and without library calls that divide for you. So build the answer from additions, subtractions, comparisons
and bit shifts.
Example 1
Input: dividend = 100, divisor = 7
14Explanation: 7 × 14 = 98 and 7 × 15 = 105, so 7 fits into 100 fourteen whole times. The 2 left over is dropped.
Example 2
Input: dividend = -2147483648, divisor = -1
2147483647Explanation: The true answer is 231 = 2147483648, one more than the largest 32-bit integer. This is the one division that does not fit, so the answer is 231 − 1.
Example 3
Input: dividend = 9, divisor = -4
-2Explanation: 9 divided by −4 is −2.25. Cutting off the fraction gives −2, not −3.
Check your understanding
Work out the answer for this input before you write any code.
Constraints
-231 ≤ dividend, divisor ≤ 231 − 1divisor ≠ 0
Clarifying questions
What you would ask an interviewer before writing any code.