Need some help understanding python solutions of leetcode 371. "Sum of Two Integers". I found https://discuss.leetcode.com/topic/49900/python-solution/2 is the most voted python solution, but I am having problem understand it.

  • How to understand the usage of "% MASK" and why "MASK = 0x100000000"?
  • How to understand "~((a % MIN_INT) ^ MAX_INT)"?
  • When sum beyond MAX_INT, the functions yells negative value (for example getSum(2147483647,2) = -2147483647), isn't that incorrect?

class Solution(object):

    def getSum(self, a, b):
        :type a: int
        :type b: int
        :rtype: int
        MAX_INT = 0x7FFFFFFF
        MIN_INT = 0x80000000
        MASK = 0x100000000
        while b:
            a, b = (a ^ b) % MASK, ((a & b) << 1) % MASK
        return a if a <= MAX_INT else ~((a % MIN_INT) ^ MAX_INT)
  • What are the stipulations here? Can only use bitwise operators and %? – Matt Messersmith Jul 24 '16 at 22:33
  • 2
    Using the % operator with bitwise operators to implement addition is slightly ridiculous. – chepner Jul 24 '16 at 23:10
  • @mwm314 yes, that is correct. Updated title. – user1269298 Jul 24 '16 at 23:41

Let's disregard the MASK, MAX_INT and MIN_INT for a second.

Why does this black magic bitwise stuff work?

The reason why the calculation works is because (a ^ b) is "summing" the bits of a and b. Recall that bitwise xor is 1 when the bits differ, and 0 when the bits are the same. For example (where D is decimal and B is binary), 20D == 10100B, and 9D = 1001B:


and 11101B == 29D.

But, if you have a case with a carry, it doesn't work so well. For example, consider adding (bitwise xor) 20D and 20D.


Oops. 20 + 20 certainly doesn't equal 0. Enter the (a & b) << 1 term. This term represents the "carry" for each position. On the next iteration of the while loop, we add in the carry from the previous loop. So, if we go with the example we had before, we get:

# First iteration (a is 20, b is 20)
10100 ^ 10100 == 00000 # makes a 0
(10100 & 10100) << 1 == 101000 # makes b 40

# Second iteration:
000000 ^ 101000 == 101000 # Makes a 40
(000000 & 101000) << 1 == 0000000 # Makes b 0

Now b is 0, we are done, so return a. This algorithm works in general, not just for the specific cases I've outlined. Proof of correctness is left to the reader as an exercise ;)

What do the masks do?

All the masks are doing is ensuring that the value is an integer, because your code even has comments stating that a, b, and the return type are of type int. Thus, since the maximum possible int (32 bits) is 2147483647. So, if you add 2 to this value, like you did in your example, the int overflows and you get a negative value. You have to force this in Python, because it doesn't respect this int boundary that other strongly typed languages like Java and C++ have defined. Consider the following:

def get_sum(a, b):
    while b:
        a, b = (a ^ b), (a & b) << 1
    return a

This is the version of getSum without the masks.

print get_sum(2147483647, 2)




 print Solution().getSum(2147483647, 2)



due to the overflow.

The moral of the story is the implementation is correct if you define the int type to only represent 32 bits.

  • For the completeness of this thread, I would like to point out two things about the algorithm and interpretation: loop inside the function and mechanism running on for the negative numbers. This is a comment and cannot contain codes nor expressions, so details will be skipped. – sdr2002 Dec 17 '19 at 18:51
  • 1. Loop: Sum of a and b keeps constant over iterations - ^ keeps all the (1,0) pairs and & << keeps the (1,1) pairs. Further, the loop gradually reduces all the 1 bits from b to a at & operation - any (a=0,b=1) occasion drops 1 bit from b - which is always the case for positive numbers. – sdr2002 Dec 17 '19 at 18:58
  • 2. The function works (perhaps only) when the integer is represented as complement notation (stackoverflow.com/questions/26315782/…). Essentially, -a is written as ~a + 1. For instance, -1 = 1|1111111 while +1 = 0|0000001 and hence (-1) + (+1) = 0|0000000. Lastly, you can also easily show that (-1)+(-1) = 1|1111110=-2 which allows the function to deal with every negative numbers. – sdr2002 Dec 17 '19 at 19:04

Here is solution works in every case

- -
- +
+ -
+ +

python default int size is not 32bit, it is very large number, so to prevent overflow and stop running into infinite loop, we use 32bit mask to limit int size to 32bit (0xffffffff)

while (b & mask):
    carry=a & b
    b=carray <<1
print( (a&Mask) if b>0 else a)

Your Answer

