**Why does this black magic bitwise stuff work?** 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: 10100 1001 ----- 11101 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. 10100 10100 ----- 00000 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 ;) ## Python solution(most upvoted) ``` 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 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) outputs 2147483649 while print Solution().getSum(2147483647, 2) outputs -2147483647 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.

bitwisee

Adding two number without (+, -) LT:371

Join Our Newsletter. No Spam, Only the good stuff.