Divide Two Integers
Divide dividend by divisor without using multiplication, division or the modulo operator, truncating toward zero. Clamp the result to the signed 32-bit range.
Intuition
Division is repeated subtraction, but subtracting the divisor one copy at a time is O(dividend) — with divisor = 1 and a dividend near 2^31 that is billions of iterations. The fix comes from how the quotient itself decomposes: every integer is a sum of powers of two. If the answer is 7, then 7 = 4 + 2 + 1, so instead of subtracting the divisor seven times we can subtract it four times at once, then twice at once, then once. And subtracting the divisor 2^k times is just a left shift. So: repeatedly find the largest shifted divisor that still fits, subtract it, and credit that power of two to the quotient.
Without / or %, subtract the largest doubled multiple of the divisor that still fits, repeatedly. Doubling means each outer iteration removes a chunk proportional to what remains, so the loop runs O(log n) times rather than O(quotient).
Approach
Write the brute force and see exactly where it dies
To compute 22 / 3, keep adding 3 until you cannot: 3, 6, 9, 12, 15, 18, 21 — seven additions, then 24 overshoots, so the answer is 7. Correct, O(quotient) time. Now set divisor = 1 and dividend = 2^31 - 1 and it performs over two billion additions. This is the version to state in an interview, immediately followed by why it fails.
Decompose the quotient into powers of two
The answer 7 can be written 2^2 + 2^1 + 2^0. Multiplying through by the divisor: 22 contains 3x2^2 = 12, then 3x2^1 = 6, then 3x2^0 = 3. So rather than removing 3 seven times, remove 12, then 6, then 3 — three steps instead of seven, and the saving grows exponentially with the quotient. Crucially, 3 << k is 3 x 2^k with no multiplication involved.
Greedily take the biggest shift that fits
At each round, double the divisor while divisor << (k+1) is still no larger than what remains. For 22 and 3: 3 fits, 6 fits, 12 fits, 24 does not — so take 12 and add 2^2 = 4 to the quotient, leaving 10. Repeat on 10: the largest fit is 6, add 2^1 = 2, leaving 4. Repeat on 4: the largest fit is 3, add 2^0 = 1, leaving 1. Now 1 is smaller than the divisor, so stop. Quotient 4 + 2 + 1 = 7. Each round strips at least one bit off the remainder, so the loop runs O(log n) times.
Handle sign and overflow separately
Do all the shifting on absolute values, and work out the sign up front: the result is negative exactly when the signs of dividend and divisor differ. The one overflow case is dividend = -2^31, divisor = -1, whose true answer 2^31 does not fit in a signed 32-bit int — return 2^31 - 1 for it, as the problem specifies.
Solution & live demo
Common pitfalls
Missing the INT_MIN / -1 overflow case
neg = (dividend < 0) != (divisor < 0)
if dividend == -2**31 and divisor == -1:
return 2**31 - 1The true quotient is 2^31, one past the maximum 32-bit signed value. Every other input fits, so this single pair needs an explicit clamp before any arithmetic happens.
Subtracting the divisor one at a time
while a >= b:
a -= b; quotient += 1while a >= (b << (power + 1)):
power += 1
a -= (b << power)Dividing a large number by 1 would loop billions of times. Doubling the subtrahend finds the answer in about 31 steps regardless of magnitude.
Determining the sign after taking absolute values
a, b = abs(dividend), abs(divisor) neg = a < 0
neg = (dividend < 0) != (divisor < 0) a, b = abs(dividend), abs(divisor)
Once both are positive the sign information is gone. The XOR of the two original signs must be captured first — and working with positives afterwards keeps the shifting logic free of sign edge cases.
Edge cases
The mathematical answer 2^31 exceeds INT_MAX. Detect this pair before any work and return 2^31 - 1.
Falls out of the general algorithm without special-casing (aside from the overflow pair above), since the shift loop simply runs to the highest power of two that fits.
The loop body never executes, the quotient stays 0, and 0 is the correct truncated-toward-zero result.
Returns 0 immediately for the same reason.