Integer division without standard operators

You're sitting in a Bloomberg interview and the interviewer asks: "Implement integer division without using multiplication, division, or the modulus operator." Your first instinct might be to subtract the divisor repeatedly, but that's a trap. The real challenge is doing it efficiently, and that's where bit manipulation comes in. This problem is also known as "Divide Two Integers" on other platforms, and it's a favorite at companies like Adobe, Apple, Amazon, and Microsoft because it tests both your understanding of low-level operations and your ability to handle tricky edge cases.

TL;DR

Divide two integers without *, /, or % by repeatedly doubling the divisor with left shifts until it exceeds the dividend, then subtracting the largest possible chunk. This runs in O(log² n) time and O(1) space. Handle the overflow edge case where Integer.MIN_VALUE / -1 exceeds the 32-bit signed range by returning Integer.MAX_VALUE. Use XOR on the sign bits to determine the result's sign, then work with absolute values.

Why This Problem Matters

Integer division without standard operators forces you to think about what division actually means at a fundamental level. Instead of reaching for a built-in operator, you need to decompose the operation into simpler primitives: subtraction and bit shifting. This kind of thinking transfers directly to embedded systems, hardware design, and any situation where you need to understand how arithmetic works under the hood. Companies test this problem because it reveals whether you can optimize beyond the obvious approach and handle integer overflow carefully.

The Naive Approach and Why It Falls Short

The most intuitive way to divide without the / operator is repeated subtraction. If you want to compute 10 / 3, just keep subtracting 3 from 10 and count how many times you can do it:

This works, and it's easy to understand. But consider dividing 2,147,483,647 by 1. You'd need over 2 billion subtractions. That's O(n) where n is the quotient, which is far too slow for interview expectations.

We need a way to subtract larger chunks at a time.

The Bit-Shift Insight

Here is the core idea: instead of subtracting the divisor once per iteration, we can double it using left shifts. A left shift by 1 (<< 1) is equivalent to multiplying by 2, but crucially, it doesn't use the multiplication operator.

For 43 / 3, the inner loop doubles the divisor:

We stop when the next doubling would exceed the remaining dividend. At that point, tempDivisor=24 fits into 43 (since 24 ≤ 43), so we subtract 24 and record that we've accounted for 8 copies of the divisor. Then we repeat the process on the remainder.

Here's the full algorithm tracing 43 / 3:

Three outer iterations instead of fourteen subtractions. The time complexity drops from O(n) to O(log² n).

Handling Signs and Overflow

Before running the main loop, we need to address two concerns.

Sign determination. The result is negative only when the dividend and divisor have opposite signs. We can detect this using XOR (or != on the sign checks):

After recording the sign, we convert both values to their absolute forms and work with positive numbers throughout.

The overflow edge case. In a 32-bit signed integer environment, values range from -2^31 to 2^31 - 1. The only division that overflows is Integer.MIN_VALUE / -1, because the result 2^31 has no 32-bit signed representation. We handle this with a guard clause at the top. In Java and C++, we also convert to long before calling Math.abs because Math.abs(Integer.MIN_VALUE) overflows in 32-bit.

Implementation

Prefer a different language? Jump to solutions in other languages.

public class Solution {

  public int divide(int dividend, int divisor) {
    // Handle the only overflow case: MIN_VALUE / -1 exceeds MAX_VALUE
    if (dividend == Integer.MIN_VALUE && divisor == -1) {
      return Integer.MAX_VALUE;
    }

    // Determine the sign of the result
    boolean negative = (dividend < 0) ^ (divisor < 0);

    // Work with positive longs to avoid abs(MIN_VALUE) overflow
    long absDividend = Math.abs((long) dividend);
    long absDivisor = Math.abs((long) divisor);

    int result = 0;

    // Outer loop: keep subtracting the largest possible chunk
    while (absDividend >= absDivisor) {
      long tempDivisor = absDivisor;
      long multiple = 1;

      // Inner loop: double the divisor until it would exceed the dividend
      while (absDividend >= (tempDivisor << 1)) {
        tempDivisor <<= 1;
        multiple <<= 1;
      }

      // Subtract the largest chunk and accumulate the multiple
      absDividend -= tempDivisor;
      result += multiple;
    }

    return negative ? -result : result;
  }
}

Walking Through the Code

Let's trace divide(10, 3) step by step:

1. Overflow check: 10 != MIN_VALUE, so we skip the guard.
2. Sign: Both positive, so negative = false.
3. Absolute values: absDividend = 10, absDivisor = 3.
4. Outer loop, iteration 1:
   • tempDivisor = 3, multiple = 1
   • Inner loop: 10 >= 6? Yes, double to tempDivisor = 6, multiple = 2
   • Inner loop: 10 >= 12? No, stop.
   • Subtract: 10 - 6 = 4, result = 0 + 2 = 2
5. Outer loop, iteration 2:
   • tempDivisor = 3, multiple = 1
   • Inner loop: 4 >= 6? No, stop immediately.
   • Subtract: 4 - 3 = 1, result = 2 + 1 = 3
6. Outer loop check: 1 >= 3? No, exit.
7. Return: negative is false, so return 3.

Complexity Analysis

Time Complexity: O(log² n)

The inner loop doubles the divisor each time, so it runs at most O(log n) times where n is the absolute value of the dividend. Each outer loop iteration removes at least half of the remaining dividend (because we found the largest power-of-two multiple), so the outer loop also runs at most O(log n) times. Since the inner loop runs up to O(log n) times per outer iteration, the total time complexity is O(log² n).

Space Complexity: O(1)

We only use a fixed number of variables (tempDivisor, multiple, result, negative) regardless of input size. No additional data structures are needed.

Common Pitfalls

1. Forgetting the overflow case. Integer.MIN_VALUE / -1 is the single combination that overflows, and missing it is the most common interview mistake for this problem.

2. Using int for absolute values. Math.abs(Integer.MIN_VALUE) returns Integer.MIN_VALUE in Java because the positive equivalent exceeds 32-bit range. Always cast to long first.

3. Infinite loops with zero divisor. The problem states the divisor is never zero, but if you're writing production code, add a guard.

4. Getting the sign logic wrong. XOR (^) is the cleanest way to check if exactly one operand is negative. Using manual if/else chains is error-prone.

5. Off-by-one in the inner loop. The condition is absDividend >= (tempDivisor << 1), not absDividend > tempDivisor. Getting this wrong either skips valid doublings or causes the shifted value to overshoot.

Interview Tips

When solving this in an interview:

1. Start by acknowledging the naive approach. Tell the interviewer you could subtract repeatedly but it's O(n). This shows you can evaluate tradeoffs.

2. Explain the bit-shift optimization. Mention that left-shifting is equivalent to multiplying by 2 without using multiplication.

3. Handle edge cases first. Write the overflow guard before the main logic. Interviewers notice when you think defensively.

4. Trace through a small example. Use 10 / 3 on the whiteboard to show your algorithm produces 3.

5. Know your follow-ups. If asked, explain that this technique is how CPUs actually implement division in hardware using shift-and-subtract circuits.

Key Takeaways

• Left-shifting the divisor (<< 1) doubles it without multiplication, letting you subtract exponentially larger chunks from the dividend in each iteration.
• The only overflow case is MIN_VALUE / -1, because abs(MIN_VALUE) exceeds the positive 32-bit range. Guard this at the top of your function.
• XOR on the sign bits cleanly determines the result sign; convert to absolute values and handle signs separately from the division logic.
• The outer loop runs O(log n) times because each iteration removes at least half the remaining dividend; the inner loop also runs O(log n) per iteration for a total O(log² n) time.
• Always cast to long before taking absolute values in Java and C++ to avoid silent overflow when the dividend is MIN_VALUE.

Practice and Related Problems

Once you're comfortable with this problem, try these related challenges to strengthen your bit manipulation skills:

• Power of Two (check if a number is a power of 2 using bit operations)
• Counting Set Bits in Binary (count the 1-bits in a number)
• Pivoted Array Target Search (another problem that uses the "halving" insight)

This problem and hundreds of others are available on Firecode, where over 50,000 engineers have prepared for technical interviews and landed roles at top tech companies. Whether you're targeting Adobe, Apple, or Amazon, mastering bit manipulation fundamentals like this will give you a real edge.

Solutions in Other Languages

Python

class Solution:
    def divide(self, dividend: int, divisor: int) -> int:
        INT_MAX = 2**31 - 1
        INT_MIN = -2**31

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

        negative = (dividend < 0) != (divisor < 0)
        dividend, divisor = abs(dividend), abs(divisor)
        quotient = 0

        while dividend >= divisor:
            temp, multiple = divisor, 1
            while dividend >= (temp << 1):
                temp <<= 1
                multiple <<= 1
            dividend -= temp
            quotient += multiple

        if negative:
            quotient = -quotient

        return max(INT_MIN, min(INT_MAX, quotient))

JavaScript

class Solution {
  divide(dividend, divisor) {
    const MAX_INT = 2 ** 31 - 1;
    const MIN_INT = -(2 ** 31);

    if (dividend === MIN_INT && divisor === -1) {
      return MAX_INT;
    }

    const isNegative = (dividend < 0) !== (divisor < 0);
    let absDividend = Math.abs(dividend);
    let absDivisor = Math.abs(divisor);
    let quotient = 0;

    while (absDividend >= absDivisor) {
      let tempDivisor = absDivisor;
      let multiple = 1;
      while (absDividend >= tempDivisor * 2) {
        tempDivisor *= 2;
        multiple *= 2;
      }
      absDividend -= tempDivisor;
      quotient += multiple;
    }

    return isNegative ? -quotient : quotient;
  }
}

module.exports = Solution;

TypeScript

class Solution {
  divide(dividend: number, divisor: number): number {
    const MAX_INT = 2 ** 31 - 1;
    const MIN_INT = -(2 ** 31);

    if (dividend === MIN_INT && divisor === -1) {
      return MAX_INT;
    }

    const isNegative = (dividend < 0) !== (divisor < 0);
    let absDividend = Math.abs(dividend);
    let absDivisor = Math.abs(divisor);
    let quotient = 0;

    while (absDividend >= absDivisor) {
      let tempDivisor = absDivisor;
      let multiple = 1;
      while (absDividend >= tempDivisor * 2) {
        tempDivisor *= 2;
        multiple *= 2;
      }
      absDividend -= tempDivisor;
      quotient += multiple;
    }

    return isNegative ? -quotient : quotient;
  }
}

export { Solution };

C++

#include <climits>
#include <cmath>

class Solution {
public:
  int divide(int dividend, int divisor) {
    if (dividend == INT_MIN && divisor == -1) {
      return INT_MAX;
    }

    bool negative = (dividend < 0) ^ (divisor < 0);
    long long absDividend = std::abs(static_cast<long long>(dividend));
    long long absDivisor = std::abs(static_cast<long long>(divisor));
    int quotient = 0;

    while (absDividend >= absDivisor) {
      long long tempDivisor = absDivisor, multiple = 1;
      while (absDividend >= (tempDivisor << 1)) {
        tempDivisor <<= 1;
        multiple <<= 1;
      }
      absDividend -= tempDivisor;
      quotient += multiple;
    }

    return negative ? -quotient : quotient;
  }
};

Go

package solution

import "math"

func (s *Solution) Divide(dividend int, divisor int) int {
    if dividend == math.MinInt32 && divisor == -1 {
        return math.MaxInt32
    }

    negative := (dividend < 0) != (divisor < 0)
    dividendAbs := abs(dividend)
    divisorAbs := abs(divisor)
    quotient := 0

    for dividendAbs >= divisorAbs {
        tempDivisor, multiple := divisorAbs, 1
        for dividendAbs >= (tempDivisor << 1) {
            tempDivisor <<= 1
            multiple <<= 1
        }
        dividendAbs -= tempDivisor
        quotient += multiple
    }

    if negative {
        return -quotient
    }
    return quotient
}

func abs(x int) int {
    if x < 0 {
        return -x
    }
    return x
}

type Solution struct{}

Scala

class Solution {
  def divide(dividend: Int, divisor: Int): Int = {
    if (dividend == Int.MinValue && divisor == -1) return Int.MaxValue

    val negative = (dividend < 0) ^ (divisor < 0)
    var dividendAbs = math.abs(dividend.toLong)
    val divisorAbs = math.abs(divisor.toLong)
    var quotient = 0

    while (dividendAbs >= divisorAbs) {
      var tempDivisor = divisorAbs
      var multiple = 1
      while (dividendAbs >= (tempDivisor << 1)) {
        tempDivisor <<= 1
        multiple <<= 1
      }
      dividendAbs -= tempDivisor
      quotient += multiple
    }

    if (negative) -quotient else quotient
  }
}

Kotlin

import kotlin.math.abs

class Solution {
  fun divide(dividend: Int, divisor: Int): Int {
    if (dividend == Int.MIN_VALUE && divisor == -1) {
      return Int.MAX_VALUE
    }

    val negative = (dividend < 0) xor (divisor < 0)
    var absDividend = abs(dividend.toLong())
    val absDivisor = abs(divisor.toLong())
    var result = 0

    while (absDividend >= absDivisor) {
      var tempDivisor = absDivisor
      var multiple = 1L
      while (absDividend >= (tempDivisor shl 1)) {
        tempDivisor = tempDivisor shl 1
        multiple = multiple shl 1
      }
      absDividend -= tempDivisor
      result += multiple.toInt()
    }

    return if (negative) -result else result
  }
}

Ruby

class Solution
  def divide(dividend, divisor)
    return 2**31 - 1 if dividend == -2**31 && divisor == -1

    negative = (dividend < 0) ^ (divisor < 0)
    abs_dividend = dividend.abs
    abs_divisor = divisor.abs
    result = 0

    while abs_dividend >= abs_divisor
      temp_divisor = abs_divisor
      multiple = 1
      while abs_dividend >= (temp_divisor << 1)
        temp_divisor <<= 1
        multiple <<= 1
      end
      abs_dividend -= temp_divisor
      result += multiple
    end

    negative ? -result : result
  end
end

Rust

pub struct Solution;

impl Solution {
    pub fn divide(&self, dividend: i32, divisor: i32) -> i32 {
        if dividend == i32::MIN && divisor == -1 {
            return i32::MAX;
        }

        let negative = (dividend < 0) ^ (divisor < 0);
        let mut abs_dividend = (dividend as i64).abs();
        let abs_divisor = (divisor as i64).abs();
        let mut result = 0;

        while abs_dividend >= abs_divisor {
            let mut temp_divisor = abs_divisor;
            let mut multiple = 1;
            while abs_dividend >= (temp_divisor << 1) {
                temp_divisor <<= 1;
                multiple <<= 1;
            }
            abs_dividend -= temp_divisor;
            result += multiple;
        }

        if negative { -result } else { result }
    }
}

Swift

class Solution {
    func divide(_ dividend: Int, _ divisor: Int) -> Int {
        if dividend == Int(Int32.min) && divisor == -1 {
            return Int(Int32.max)
        }

        let negative = (dividend < 0) != (divisor < 0)
        var absDividend = abs(dividend)
        let absDivisor = abs(divisor)
        var result = 0

        while absDividend >= absDivisor {
            var tempDivisor = absDivisor
            var multiple = 1
            while absDividend >= (tempDivisor << 1) {
                tempDivisor <<= 1
                multiple <<= 1
            }
            absDividend -= tempDivisor
            result += multiple
        }

        return negative ? -result : result
    }
}

Dart

class Solution {
  int divide(int dividend, int divisor) {
    if (dividend == -2147483648 && divisor == -1) {
      return 2147483647;
    }

    bool negative = (dividend < 0) ^ (divisor < 0);
    int absDividend = dividend.abs();
    int absDivisor = divisor.abs();
    int result = 0;

    while (absDividend >= absDivisor) {
      int tempDivisor = absDivisor;
      int multiple = 1;
      while (absDividend >= (tempDivisor << 1)) {
        tempDivisor <<= 1;
        multiple <<= 1;
      }
      absDividend -= tempDivisor;
      result += multiple;
    }

    return negative ? -result : result;
  }
}

C#

using System;

public class Solution {
    public int divide(int dividend, int divisor) {
        if (dividend == int.MinValue && divisor == -1) {
            return int.MaxValue;
        }

        bool negative = (dividend < 0) ^ (divisor < 0);
        long absDividend = Math.Abs((long)dividend);
        long absDivisor = Math.Abs((long)divisor);
        int result = 0;

        while (absDividend >= absDivisor) {
            long tempDivisor = absDivisor;
            long multiple = 1;
            while (absDividend >= (tempDivisor << 1)) {
                tempDivisor <<= 1;
                multiple <<= 1;
            }
            absDividend -= tempDivisor;
            result += (int)multiple;
        }

        return negative ? -result : result;
    }
}

PHP

<?php

class Solution {
    public function divide(int $dividend, int $divisor): int {
        $maxInt = 2147483647;
        $minInt = -2147483648;

        if ($dividend === $minInt && $divisor === -1) {
            return $maxInt;
        }

        $negative = ($dividend < 0) !== ($divisor < 0);
        $absDividend = abs($dividend);
        $absDivisor = abs($divisor);
        $result = 0;

        while ($absDividend >= $absDivisor) {
            $tempDivisor = $absDivisor;
            $multiple = 1;
            while ($absDividend >= ($tempDivisor << 1)) {
                $tempDivisor <<= 1;
                $multiple <<= 1;
            }
            $absDividend -= $tempDivisor;
            $result += $multiple;
        }

        return $negative ? -$result : $result;
    }
}