LC 371 - Sum of Two Integers

Question

Given two integers a and b, return the sum of the two integers without using the operators + and -.

Example 1:

Input: a = 1, b = 2
Output: 3

Example 2:

Input: a = 2, b = 3
Output: 5

Constraints:

• -1000 <= a, b <= 1000

Links

Question here and solution here

Solution

concept

We will need to use XOR to add the two num digit-wise, this will give us desired behaviour for addition on the least significant bit, but not carry We will then need to use AND to get the case where both element is 1, which results a 0 and therefore results a carry, this carry is then shifted to the left to be added in again By add again we need to repeat the XOR and (shifted) AND operation again until there is no more carry

code

class Solution:
    def getSum(self, a: int, b: int) -> int:
        mask = 0xffffffff

        while b != 0:
            tmp = (a & b) << 1
            a = (a ^ b) & mask
            b = tmp & mask

        if a > mask // 2:
            return ~(a ^ mask)
        else:
            return a

To explain, the hexadecimal number 0xffffffff is the same as the binary number 0b1111111111111111111111111111111, containing 32 1’s. (It’s just easier to type) In order to make the code work like Java, we want to treat our numbers like they only have 32 bits. ANDing a number with the mask 0xffffffff, or 32 1’s, basically turns all of a number’s bits into 0’s except for the rightmost 32. As a result, the number can be represented as if it only has 32 bits. We do what Neetcode describes in his video, using XOR for the sum and AND for the carry. We AND with the mask each time we set a and b in order to keep our numbers within 32 bits. After we exit the while loop, we have our answer a.

If a is positive, then we can return it directly. However, in Python, negative numbers are represented in binary as having an unlimited number of leading 1’s. The current answer would only have values in the rightmost 32 bits. Therefore, if the answer is negative, we need to convert it into Python’s representation of negative numbers. First, we need to check if the answer is negative. We cannot just check to see if the answer is less than zero because our representation of the answer is not the same as Python’s (since Python’s have unlimited leading 1’s). We are still treating our answer as if it only fits into 32 bits. A 32-bit signed integer is positive if the 32nd bit is a 0 and is negative if the 32nd bit is a 1. If we divide our mask (0xffffffff) by 2, we will get the binary number 0b0111111111111111111111111111111, which has 31 1’s. This number is the greatest value we can have before the 32nd bit becomes a 1. Therefore, if our answer a > mask // 2, it is negative. Otherwise, it is positive and we can just return a itself. If the number is negative, we then need to convert it into Python’s representation of negative numbers. To do so, we can XOR with the mask of 32 1’s in order to flip the rightmost 32 bits, since XORing a bit with 1 flips the bit. We can then NOT the number in order to turn all of the leading 0’s into 1’s.

For example, say that the answer is -3, and (….0000000) or (….1111111) denote leading 0’s or 1’s until the 32nd bit: Our representation of -3 in 32 bits: (…0000000)11111111111111111111111111111101 XOR with mask, aka flip rightmost 32 bits: (…0000000)00000000000000000000000000000010 NOT, aka flipping all bits: (…1111111)1111111111111111111111111111101 The result is Python’s representation of -3, including an unlimited number of leading 1’s. Overall, the code uses the same process as Neetcode’s Java code, but with masking to get numbers into 32 bits and some manipulation to get those 32-bit numbers back into Python’s representation before returning.

Complexity

time: $O(1)$
space: $O(1)$