Blind 75.11 - Sum of Two Integers

Sum of two integers.

Problem description

Taken directly from LeetCode.

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

Solution type

Doesn’t really fit in any cateogry, although you could call it recursion.

Solution

We can do a naive addition algorithm similar to how it’s done in grade school: add the last digits together, carry, add the next digits, carry, etcetera. We can’t use the + operator to add, so we have to work around it using other bit operators.

def getSum(self, a: int, b: int) -> int:
    ret = 0
    currentDigit, carry = 1, 0
    while a != 0 or b != 0:
        lastOfA, lastOfB = a & 1, b & 1
        if lastOfA ^ lastOfB ^ carry:
            ret = ret | currentDigit
        if (lastOfA and lastOfB) or (lastOfA and carry) or (lastOfB and carry):
            carry = 1
        else:
            carry = 0
        a, b = a >> 1, b >> 1
        currentDigit = currentDigit << 1
    if carry:
        ret = ret | currentDigit
    return ret

This isn’t correct - it doesn’t work on negative numbers, and in fact it will loop infinitely in LeetCode Python. This is weird to me? I’m pretty sure Python integers are still 32-bit or 64-bit; they shouldn’t go on infinitely. Going to look that up later.

There’s a better way to do this anyway. Looking at both numbers bitwise, a + b = a ^ b + (a & b) << 1, where a ^ b represents the addition without considering carry and (a & b) << 1 represents the result of adding the carry. The carry bits are shifted by one because you should be adding them one place to the left. We still have a + on the left, but using recursion¹ we can assign a' = a ^ b and b' = (a & b) << 1 and run our addition algorithm again. We repeat until we have no carry bits, then return our final sum.

Still doesn’t work on negative numbers though:

def getSum(self, a: int, b: int) -> int:
    sum, carry = a ^ b, a & b
    i = 0
    while carry > 0 and i < 64:
        carry = carry << 1
        a, b = sum, carry
        sum, carry = a ^ b, a & b
        i += 1
    return sum

I think what’s happening is that if the integer overflows, Python converts it into a bigger type. In C or C++, integers are fixed-width (32 bits on most modern systems), so eventually you will hit a point where the right shift operator << “erases” digits. For example, with a 2-byte short such as short x = 0xff, if you right shift by 4 by doing x = x << 4, x will be equal to 0xf0; the most significant four bits go “out of bounds” and are lost to the void.

To explain why this is an issue with negative numbers specifically: the standard representation for negative numbers is two’s complement. For an 8-bit integer, -1’s representation is 0b1111 1111; for a 32-bit integer, -1’s representation is 0xffff. The most significant bit is the sign bit. If the sign bit is 1, then the number is negative; else it is positive. (More specifically, for a short the value of the number is -1 * (value of MSB) * \(2^{32}\) + (value of 2nd MSB) * \(2^{31}\) + … + (value of least significant bit) * \(2^0\).)

The stupid solution is to case on negative numbers. If the signs of the numbers match, then find the sum. Else, find the difference.

def getSum(self, a: int, b: int) -> int:
    if abs(a) < abs(b):
        a, b = b, a
    aSign, bSign = 1 if a > 0 else -1, 1 if b > 0 else -1
    isAddition = aSign == bSign
    a, b = max(abs(a), abs(b)), min(abs(a), abs(b))

    if isAddition:
        sum, carry = a ^ b, a & b
        while carry > 0:
            carry = carry << 1
            a, b = sum, carry
            sum, carry = a ^ b, a & b
    else:
        sum, carry = a ^ b, ~a & b
        while carry > 0:
            carry = carry << 1
            a, b = sum, carry
            sum, carry = a ^ b, ~a & b
    return sum * aSign

For “carry” bits in subtraction, you care about the case where the digit in a is 0 and the digit in b is 1, so you check ~a & b instead of a & b. Other than that, there’s some additional logic to make sure the sign is correct regardless what operation you do.

Considering that two’s complement is supposed to make addition of positive and negative numbers the same operation, this does not feel elegant, even if it passes. Addition ought to be the same regardless of the number.

I did some more research and it looks like the problem of never reaching the most significant bit isn’t a LeetCode issue, but something built into Python by design? I need to look more into this. This shouldn’t actually have been a problem because if you read the problem statement closely, you only need the last 11 bits; The problem statement limits you to values with absolute value less than 1024, and you’d need the 11th bit for sign, so we could’ve used a & 0x7ff, b & 0x7ff. Oh well. It was a good exercise to figure out how subtraction works.

1. I just used a while loop because it came to me easier in this situation. ↩