Bit Manipulation - Divide Two Integers

Given two integers dividend and divisor, divide two integers without using multiplication, division, or mod operator. The integer division should truncate toward zero. If the answer cannot be represented due to integer overflow, return 2^31 - 1.

Input: dividend = 10, divisor = 3
Output: 3
Explanation: 10 / 3 = 3.333... truncated to 3.

Input: dividend = 7, divisor = -3
Output: -2
Explanation: 7 / -3 = -2.333... truncated to -2.

Work with long values to avoid overflow. Use bit shifting to find the largest multiple of divisor that fits into dividend: double the divisor repeatedly (left shift) to find how many times it fits, then subtract and repeat. The sign is determined separately.

Handle overflow edge case: dividend = Integer.MIN_VALUE and divisor = -1 returns Integer.MAX_VALUE.
Work with absolute values, track the sign separately.
For each step, find the largest shift such that (divisor << shift) <= remaining dividend.
Add 1 << shift to the quotient and subtract from dividend.
Apply sign and clamp to 32-bit range.

class Solution { public int divide(int dividend, int divisor) { if (dividend == Integer.MIN_VALUE && divisor == -1) return Integer.MAX_VALUE; long dvd = Math.abs((long) dividend); long dvs = Math.abs((long) divisor); boolean negative = (dividend < 0) ^ (divisor < 0); long quotient = 0; while (dvd >= dvs) { long temp = dvs, multiple = 1; while (dvd >= (temp << 1)) { temp <<= 1; multiple <<= 1; } dvd -= temp; quotient += multiple; } return (int) (negative ? -quotient : quotient); } }

Complexity Analysis:

Time complexity: O(log^2 n) — outer loop runs O(log n) times, inner loop also O(log n).
Space complexity: O(1) — constant extra space.