Divide using shifts

Implement integer division using only bit shifts and basic arithmetic, no division or modulo operators.

integer division bit shifts overflow edge cases

Write a function `divide(dividend: int, divisor: int) -> int` that performs integer division of `dividend` by `divisor`, truncating toward zero, as in Python's `//` for positive results but handling negatives correctly. Your implementation must NOT use the division operator `/` or the modulo operator `%`, nor any functions like `math.floor` or `int()` conversion from float division. You may use addition, subtraction, multiplication, comparison, and bitwise operators (`<<`, `>>`, `&`, `|`, `^`, `~`).

Rules:
- If `divisor == 0`, raise a `ValueError` with the message `"division by zero"`.
- Truncate toward zero (e.g., `divide(-7, 2) == -3` and `divide(7, -2) == -3`).
- If the result would overflow a 32-bit signed integer (i.e., less than `-2**31` or greater than `2**31 - 1`), return the clamped value `-2**31` or `2**31 - 1` respectively. This is the same behavior as many languages' 32-bit integer division.

Examples:
- `divide(10, 3)` → `3`
- `divide(7, -3)` → `-2`
- `divide(-2147483648, -1)` → `2147483647` (clamped because `2147483648` overflows)
- `divide(0, 5)` → `0`

Your solution must handle large inputs (up to ±2^31) without using Python's arbitrary-precision division. Use bit operations to find the quotient.

Constraints

`dividend` and `divisor` are integers within the range `[-2**31, 2**31 - 1]`. `divisor` may be zero. The expected time complexity is O(log dividend) due to bit shifts.

Example

```python
>>> divide(10, 3)
3
>>> divide(7, -3)
-2
>>> divide(-2147483648, -1)
2147483647
>>> divide(0, 5)
0
>>> divide(1, 0)
ValueError: division by zero
```

20 points ~20 min

Recent Submissions

No submissions yet — hit Run Tests to try!

Hints

Work with absolute values first, then apply the sign at the end.

To find the quotient, try to subtract the largest possible shifted divisor from the dividend, similar to long division.

Be careful with the overflow case when dividend is -2**31 and divisor is -1.

Use a loop to double the divisor using left shift until it exceeds the dividend, then subtract and accumulate.

Test Results

Press Ctrl+Enter or click Run Tests to execute your code.