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.
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
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.