Python solution with no "+-*/%", completely bit manipulation guaranteed

  • 48
    class Solution(object):
        def getSum(self, a, b):
            :type a: int
            :type b: int
            :rtype: int
            # 32 bits integer max
            MAX = 0x7FFFFFFF
            # 32 bits interger min
            MIN = 0x80000000
            # mask to get last 32 bits
            mask = 0xFFFFFFFF
            while b != 0:
                # ^ get different bits and & gets double 1s, << moves carry
                a, b = (a ^ b) & mask, ((a & b) << 1) & mask
            # if a is negative, get a's 32 bits complement positive first
            # then get 32-bit positive's Python complement negative
            return a if a <= MAX else ~(a ^ mask)

  • 2

    Can someone explain to me why we need 'mask'? I understand that mask is a 32 bit with all ones, but can't &1 be reduced? Thanks in advance.

    In addition, would it be neccessary to check for outflow in the case of two large positive and two small negative?

  • 21

    @dongxinzhuo Python has more than 32 bits for integers. You can try to run "print 2 ** 31"and Python would shows the exact number correctly, while other languages like Java would not. Java only recognizes -2 ** 31 to 2 ** 31 - 1.

    How does integers presented in Python differ from integers in 32-bit e.g. Java?
    From what I heard, Python has 64 bits. (Please let me know if I am wrong. )
    So 1 in Python would look like 0x0000000000000001, but it looks like 0x00000001 in 32-bit format.
    -1 in Python would look like 0xFFFFFFFFFFFFFFFF, but it looks like 0xFFFFFFFF in 32-bit format.

    It seems that the input given by LC is in 32-bit format. Since Python would treat it as positive with 1 on the 32 position, we have to use mask to treat it as negative.

  • 1

    Cloud you mind to explain how '' ~(a ^ mask) '' works?
    For example, a = -32, b = -32, if we don't handle the negative situation, we will get the result: 4294967232. If we convert the number to binary, it seems the complement of -64 in 32-bit integer based. So how the '' ~(a^mask)'' make the 4294967232 to -64, what is principle?

  • 14

    @leeprimer For example, if a is -2 after the loop, a would be 0x00000000FFFFFFFE. What ^mask does here is get a's 32-bit complement, so a^mask = 0x0000000000000001. FYI, this is exactly what ~ in Java would do, -2 in Java is 0xFFFFFFFE, its 32-bit complement is 0x00000001 in Java. Since the output needs to be in 64-bit to be check by OJ, we want 64-bit -2. ~ in Python would convert 0x0000000000000001 to 0xFFFFFFFFFFFFFFFE, which is -2 in Python.

    In sum, you can consider a^mask gets a's 32-bit positive complement with more 32-bit 0's on left, and ~ gets the common Python complement.

    Basically, this OJ gives us 32-bit integers as input and expects 64-bit integers as output.

  • 0

    A great, well explained solution.

  • 0
    This post is deleted!

  • 1

    Hi, i think it's a good solution, but how to prove the loop could stop(i.e., a and b will have no double 1s after some iterations)?


  • 0

    @ranchenwei Think about what b actually is. It is a carry, so it moves 1s towards higher position in 32 bits. Since it moves 1s towards the highest bit and the highest bit is finite 32, it will surely end.

  • 0

    Considering the compliment switching on ~(a ^ mask), there's an alternative way to do this, which is (a|~mask). It also helps trim the bits and keeps the value.

  • 0

    solve the problem I met in this question! Good understanding for Python and Java.

  • 0

    excellent solution! thank you for your sharing

  • 0

    thanks for your share
    I wonder if there is better solution for effective time complexity

  • 1

    Python is good for manipulating big integers that exceed max length. In fact it can deal with arbitrary length integer. But that also makes infinite loop if we don't stop at max length.

  • 0

    The mask is completely necessary in Python since according to Python's official doc page:
    A left shift by n bits is equivalent to multiplication by pow(2, n). A long integer is returned if the result exceeds the range of plain integers.
    Long integers have unlimited precision.

  • 0

  • 0

    @StefanPochmann mistype. shoulda been python doc.

Log in to reply

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