class Solution:
# @return an integer
def divide(self, dividend, divisor):
positive = (dividend < 0) is (divisor < 0)
dividend, divisor = abs(dividend), abs(divisor)
res = 0
while dividend >= divisor:
temp, i = divisor, 1
while dividend >= temp:
dividend = temp
res += i
i <<= 1
temp <<= 1
if not positive:
res = res
return min(max(2147483648, res), 2147483647)
Clear python code


@tusizi said in Clear python code:
return min(max(2147483648, res), 2147483647)
Why does there need a
max()
? I thinkres
won't less than2147483648
, Am I right?

@zsn1994 its actually a XOR operation. It's for checking both dividend, divisor are positive or negative. Hope it helps


@bdeng3 a << b, move a bitwise to the left by b units. For example, a = 3, in binary 11. Then a << 2 in binary is 1100, which is 12 in decimal.

@symplecticgeometry Wow, thank you! So it's basically multiplying the number on the left by a number of 2. Say a <<= 3, it's equal to a = (2**3) * a. Is that correct..?



@zsn1994
It will make sure both dividend and divisor are positive or negative. ie. the result  dividend/divisor will be positive.

What could be complexity of this?
while dividend >= divisor: temp, i = divisor, 1 while dividend >= temp: dividend = temp res += i i <<= 1 temp <<= 1
If inner loop runs for say x times, then D gets doubled x times so that
D*2^x > N => x > log(N/D) => O(log(N/D))
And about outer loop
N = 2^x * D + M => such that N > M > D
So next time inner loop will run for log(M/D)
So its basicallylog(N/D) + log(M/D) + log(L/D) + ..... + log(D/D) => log(N/D) * Y
If someone can help simplify for Y, it would be great