Divide Two Integers: Bit Shifting Without Multiplication

Divide Two Integers is LeetCode 29. Given two integers dividend and divisor, divide them without using multiplication, division, or the mod operator. Return the quotient truncated toward zero. If the quotient overflows the 32-bit signed integer range [-2**31, 2**31 - 1], return 2**31 - 1.

A few examples:

• dividend = 10, divisor = 3 returns 3 (truncate toward zero)
• dividend = 7, divisor = -2 returns -3
• dividend = -2147483648, divisor = -1 returns 2147483647 (overflow clamped)

The constraint against multiplication, division, and mod means you need a different way to figure out how many times the divisor fits into the dividend. The naive answer is repeated subtraction, but that is far too slow. The real solution uses bit shifts to subtract exponentially larger chunks.

The approach

Subtracting the divisor one at a time works but takes O(n) time where n is the quotient. For dividend = 2**31 - 1 and divisor = 1, that is over two billion iterations.

The key insight is that left-shifting a number by one bit doubles it, and you can use this to find the largest power-of-two multiple of the divisor that fits inside the remaining dividend. Subtract that chunk, add the corresponding power of two to the quotient, and repeat.

Here is the process for 43 / 3:

1. Find the largest k where 3 << k is still at most 43. That is k = 3 because 3 << 3 = 24 fits but 3 << 4 = 48 does not.
2. Subtract 24 from 43, leaving 19. Add 1 << 3 = 8 to the quotient.
3. Now find the largest k where 3 << k fits in 19. That is k = 2 because 3 << 2 = 12 fits but 3 << 3 = 24 does not.
4. Subtract 12 from 19, leaving 7. Add 1 << 2 = 4 to the quotient.
5. Find the largest k where 3 << k fits in 7. That is k = 1 because 3 << 1 = 6 fits but 3 << 2 = 12 does not.
6. Subtract 6 from 7, leaving 1. Add 1 << 1 = 2 to the quotient.
7. Now the remainder (1) is less than the divisor (3), so you stop. Quotient = 8 + 4 + 2 = 14.

Each outer iteration finds the right shift value, which is an inner loop of at most ~31 steps. The remainder shrinks by at least half each time, so the outer loop runs at most O(log n) times.

Python solution

def divide(dividend, divisor):
    INT_MAX = 2**31 - 1
    INT_MIN = -(2**31)

    if dividend == INT_MIN and divisor == -1:
        return INT_MAX

    sign = -1 if (dividend < 0) ^ (divisor < 0) else 1
    a = abs(dividend)
    b = abs(divisor)

    quotient = 0
    while a >= b:
        shift = 0
        while a >= (b << (shift + 1)):
            shift += 1
        quotient += 1 << shift
        a -= b << shift

    return sign * quotient

Visual walkthrough

Here is the algorithm traced step by step on divide(43, 3). Each step finds the largest power-of-two chunk that fits, subtracts it, and adds the corresponding power of two to the quotient.

Notice how each iteration removes a large chunk. Three steps handle what would take 14 iterations with simple repeated subtraction. The doubling via bit shifts is what makes this fast.

Complexity analysis

The O(log^2 n) time comes from two nested logarithmic loops. The outer loop runs at most O(log n) times because each subtraction removes at least half the remaining value. The inner loop scans up to O(log n) shift positions to find the largest fit.

Building blocks

This problem decomposes into two reusable pieces that appear across many math and bit manipulation problems.

Bit shifting for doubling

Left-shifting a value by 1 doubles it. Left-shifting by k multiplies by 2**k. This is the same operation you use in binary search variants, power-of-two checks, and any problem where you need fast doubling without multiplication.

x << 1   # x * 2
x << k   # x * 2**k

Exponential subtraction

Instead of subtracting a fixed amount each iteration (linear), you find the largest power-of-two multiple that fits and subtract that (logarithmic). This pattern is conceptually similar to binary search: you eliminate large portions of the search space in each step rather than scanning one element at a time.

The combination of these two bricks turns an O(n) repeated subtraction into an O(log^2 n) algorithm.

Edge cases

Overflow: dividend = -2**31 and divisor = -1. The result would be 2**31, which exceeds the 32-bit signed max of 2**31 - 1. You must check for this case explicitly and return 2**31 - 1.

Divisor is 1. The quotient equals the dividend. The algorithm handles this correctly because b << 0 = b = 1 fits into any nonzero a, and the shift loop finds the exact binary representation of a.

Divisor is -1. Same as divisor = 1 but with the sign flipped. The overflow case above is the only special scenario.

Dividend is 0. The while loop condition a >= b fails immediately, so the quotient stays 0. Correct.

Negative numbers. The algorithm works with absolute values and restores the sign at the end. XOR on the sign bits ((dividend < 0) ^ (divisor < 0)) determines whether the result is negative.

Both negative. If both inputs are negative, XOR gives false, so the result is positive. For example, -10 / -3 = 3.

From understanding to recall

The exponential subtraction approach is easy to follow when someone explains it. The bit shift doubling makes intuitive sense. But reproducing the nested loop structure from scratch, getting the shift direction right, and remembering the overflow edge case all require practice.

There are two building blocks worth drilling independently. First, the bit-shift doubling pattern: write b << shift to double the divisor and 1 << shift to track the quotient contribution. Second, the outer loop structure: keep subtracting the largest power-of-two chunk until the remainder drops below the divisor. Each piece takes under a minute to type. Once both are in muscle memory, you can assemble them on demand.

If you have already drilled bit manipulation fundamentals from problems like Number of 1 Bits, the shift operations here will feel familiar. The new piece is using shifts for exponential subtraction rather than for isolating individual bits.

Related posts

• Number of 1 Bits - Another bit manipulation problem that builds fluency with shift operators and bitwise AND, the same primitives used in the inner loop here.
• Reverse Integer - Uses the same 32-bit overflow handling pattern and works with absolute values plus a sign flag.