Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Sum of Two Integers without using "+" operator in python

Tags:

python

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)
like image 386
user1269298 Avatar asked Jul 24 '16 22:07

user1269298


People also ask

How can we find the sum of two numbers without using operator in Python?

For example, if x and y are the numbers to be added, you can calculate (x & y) << 1 and add the result to x ^ y to get the desired sum.

How do you find the sum of two integers without using the operator?

We can use printf() to find sum of two numbers as printf() returns the number of characters printed. The width field in printf() can be used to find the sum of two numbers. We can use '*' which indicates the minimum width of output.

How do you find the sum without using the operator?

Write a function Add() that returns sum of two integers. The function should not use any of the arithmetic operators (+, ++, –, -, .. etc). Sum of two bits can be obtained by performing XOR (^) of the two bits. Carry bit can be obtained by performing AND (&) of two bits.


1 Answers

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:

 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 ;)

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.

like image 127
Matt Messersmith Avatar answered Nov 09 '22 23:11

Matt Messersmith