idea:

keep subtracting the new divisor `div`

from the remaining `left`

and then doubling `div`

(by `div += div`

). if `left < div`

, start from the original divisor. Do these until `left < divisor.`

```
def divide(self, dividend, divisor):
neg=( (dividend < 0) != (divisor < 0) )
dividend = left = abs(dividend)
divisor = div = abs(divisor)
Q = 1
ans = 0
while left >= divisor:
left -= div
ans += Q
Q += Q
div += div
if left < div:
div = divisor
Q = 1
if neg:
return max(-ans, -2147483648)
else:
return min(ans, 2147483647)
```

Recursive version:

```
def divide(self, dividend, divisor):
neg=( (dividend < 0) != (divisor < 0) )
dividend = left = abs(dividend)
divisor = div = abs(divisor)
if dividend < divisor:
return 0
Q = 1
ans = 0
while left >= div:
left -= div
ans += Q
Q += Q
div += div
if neg:
return max(-(ans + self.divide(left, divisor)), -2147483648)
else:
return min(ans + self.divide(left, divisor), 2147483647)
```