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)
return min(max(-2147483648, res), 2147483647)
Why does there need a
max()? I think
res won't less than
-2147483648, Am I right?
what's the meaning of " (dividend < 0) is (divisor < 0) "? I never saw such syntax, could you please explain it ?
@zsn1994 its actually a XOR operation. It's for checking both dividend, divisor are positive or negative. Hope it helps
@durgaharish1993 Thank you very much! Now I understand.
Hi, can anyone tell me what's "<<=" mean? I searched for it but the explanation is pretty rare.
@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..?
@bdeng3 That is correct. BTW, you should use a << 3 instead of a <<= 3
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 basically
log(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
Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.