Implement integer division without using division

You are given two 32-bit signed integers dividend and divisor.

Implement a function that divides dividend by divisor and returns the integer quotient, without using the multiplication *, division /, or modulo % operators.

The result should be truncated toward zero (i.e., rounded toward 0, not toward −∞ or +∞).

Assume:

• divisor is not zero.
• The range of 32-bit signed integers is from −2³¹ to 2³¹ − 1.

You must:

• Handle potential overflow correctly. If the result overflows the 32-bit signed integer range, return 2^31 - 1 (the maximum 32-bit signed integer).
• Aim for a time complexity better than O(|dividend|) (i.e., you should not subtract divisor from dividend one unit at a time).

Function signature example (language-agnostic):

int divide(int dividend, int divisor);

Explain the algorithm you would use and then implement the function in the programming language of your choice.

Implement Integer Division Without Using Division

Constraints

• -2^31 <= dividend <= 2^31 - 1
• -2^31 <= divisor <= 2^31 - 1
• divisor != 0
• Do not use multiplication (*), division (/), or modulo (%) operators
• The algorithm should be better than O(|dividend|)

Examples

Example 1

Input: (10, 3)
Output: 3

Explanation: 10 divided by 3 is 3.333..., which truncates toward zero to 3.

Example 2

Input: (7, -3)
Output: -2

Explanation: 7 divided by -3 is -2.333..., which truncates toward zero to -2.

Hints

1. Instead of subtracting the divisor one time at a time, try subtracting the largest doubled version of the divisor that fits into the remaining dividend.
2. Bit shifts can be used to efficiently double numbers and build the quotient from powers of two.