Clean solution with Bit Manipulation


  • 1

    A non-negative integer can be represented as a0*2^0 + a1*2^1 + a2*2^2 + ... + an*2^n, so given x, we can calculate a0, a1, a2, ..., an as:

    def getA(x):
        bit = 1
        while bit < x:
            bit <<= 1
    
        A = []
        while bit:
            a = bit <= x
            A.append(a)
    
            x -= a * bit
            bit >>= 1
    
        return A
    

    If dividend = div * divisor + mod, and div can be represented as a0*2^0 + a1*2^1 + a2*2^2 + ... + an*2^n, then dividend = (a0*2^0 + a1*2^1 + a2*2^2 + ... + an*2^n) * divisor + mod. So we just need to calculate a0, a1, a2, ... an, and we will get div.

    According above, we have below solution, be aware of overflow situations.

    class Solution(object):
        def divide(self, dividend, divisor):
            MAX_INT, MIN_INT = 2 ** 31 - 1, -2 ** 31
    
            if divisor == 0 or dividend == MIN_INT and divisor == -1:
                return MAX_INT
    
            negative = (dividend < 0) != (divisor < 0)
            dividend, divisor = map(abs, (dividend, divisor))
    
            bit = 1
            while divisor < dividend:
                divisor <<= 1
                bit <<= 1
    
            r = 0
            while bit:
                if divisor <= dividend:
                    dividend -= divisor
                    r += bit
    
                bit >>= 1
                divisor >>= 1
    
            return -r if negative else r

  • 0
    M

    using '*' is not allowed...


  • 0

    It's just for simplicity for a can only be '0' or '1', you can use if instead. And for no misunderstanding, I will change it. Thanks anyway.


Log in to reply
 

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