Python O(log n), doubling divisor then halving. Is it better?


  • 0
    Y

    I repeatedly double (bitwise <<) the divisor until the next doubling would make it more than the dividend. Then take the divisor off the dividend, half the divisor and check if it's greater then the remaining dividend, if so subtract it from the divisor etc. This subtracts from the dividend all possible powers of 2 multiplied by the divisor.
    I've seen solutions that have a while loop inside another while loop. Is this better than that?

        def divide(self, dividend, divisor):
    
            if divisor == 0:
                return None
            diff_sign = (divisor < 0) ^ (dividend < 0)
            dividend = abs(dividend)
            divisor = abs(divisor)
    
            result = 0
            max_divisor = divisor
            shift_count = 1
    
            while dividend >= (max_divisor << 1):
                max_divisor <<= 1
                shift_count <<= 1
    
            while shift_count >= 1:
                if dividend >= max_divisor:
                    dividend -= max_divisor
                    result += shift_count
                shift_count >>= 1
                max_divisor >>= 1
    
            if diff_sign:
               result = -result
            return max(min(result, 2**31-1), -2**31)
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.