Sum of Two Integers

The problem

You are given two whole numbers a and b. Each can be negative, zero or positive. Return their sum, worked out without using the + or - operators anywhere in your code. What you return must be the ordinary sum: for 2 and 3 it is 5, and for -5 and -7 it is -12.

What to write

function solve(a: number, b: number): number

Input
a = 1
b = 2

Output
3

Input
a = 2
b = 3

Output
5

Constraints

Inputs and their sum fit a signed 32-bit integer.

Hints

Each hint gives away a little more. Open one only when you need it.

1. Hint 1: Use the constraints

   Both numbers and their sum fit in a signed 32-bit integer: a whole number stored as 32 binary digits, from -2,147,483,648 through 2,147,483,647. So there are only 32 columns of digits to deal with, however large the numbers are. Negative numbers are allowed, so your method must work for them too.

2. Hint 2: Ask a smaller question

   Add two binary digits on paper, as one column: 0 and 0, then 0 and 1, then 1 and 1. In which cases is the digit you write down a 1? In which case do you carry a 1 into the next column?

3. Hint 3: Name the pattern

   The digit you write is 1 when the two bits differ: that is XOR. You carry when both bits are 1: that is AND, and a carry belongs one place to the left, which a left shift does. Building a sum from these operators is bit manipulation. The signal: arithmetic is ruled out, so only the bits are left. Read the lesson on bit manipulation.

4. Hint 4: State the invariant

   After every round, the first number plus the second number is still the sum you want, counted on 32 bits: a carry past the leftmost bit is dropped. The first holds the columns added without carries, and the second holds the carries. The carries move at least one place left each round, so they run out.

5. Hint 5: Sketch the pseudocode

   While b is not 0: carry = (a AND b) shifted left by one place, a = a XOR b, b = carry. Then return a. In Python, also cut a, b and each carry to 32 bits, and turn a result whose leftmost bit is 1 back into a negative number. JavaScript's bit operators already do both.

Solution

From here on the page gives the method away. If you are still solving, go back to the hints.

Approach

XOR adds bits without carrying, while AND shifted left computes carries. Repeat until no carries remain.

The slow way

The obvious way is to write a + b, and that is what the problem rules out. Counting up by 1 as many times as b says does not help either: it needs + as well, and it could take about two billion rounds. So the question is how addition itself is built from smaller operations.

The insight

Add two binary numbers on paper, column by column. Where the two bits differ, the column's digit is 1. Where both are 1, the digit is 0 and a 1 is carried to the next column on the left. XOR gives all the digits at once. AND finds the carries, and a shift left by one moves them into place. Adding digits and carries is the same task again.

Step by step

1. Repeat while the second number is not 0. The second number is what still has to be added to the first. At the start that is all of b. In later rounds it holds only carries. At 0, nothing is left to add.
2. Find the carries: a 1 where both bits are 1, moved one place left. In binary, 1 plus 1 is 10: write 0 and carry 1. AND, written &, keeps a 1 only where both bits are 1. The shift, << 1, moves each carry to the column that receives it.
3. Add the columns without carrying: a 1 where the two bits differ. Leave the carries out and a column's digit is 1 when exactly one of its two bits is 1: 0 and 1 make 1, while 1 and 1 make 0. That is XOR, written ^.
4. The carries become the second number, still to be added. The sum you want is the carry-free result plus the carries. That is a new addition of the same kind, so the same loop does it: the carries take the place of b.
5. No carry is left, so the first number is the sum. On 32 bits the pair always adds up to the sum you want, and the second number is now 0. In Python the reference turns 32 bits that begin with a 1 back into a negative number: 4,294,967,284 becomes -12.

The same numbered steps are the comments in each solution.

function solve(a, b) {
  // 1. Repeat while the second number is not 0
  while (b !== 0) {
    // 2. Find the carries: a 1 where both bits are 1, moved one place left
    const carry = (a & b) << 1;
    // 3. Add the columns without carrying: a 1 where the two bits differ
    a = a ^ b;
    // 4. The carries become the second number, still to be added
    b = carry;
  }
  // 5. No carry is left, so the first number is the sum
  return a;
}

function solve(a: number, b: number): number {
  // 1. Repeat while the second number is not 0
  while (b !== 0) {
    // 2. Find the carries: a 1 where both bits are 1, moved one place left
    const carry = (a & b) << 1;
    // 3. Add the columns without carrying: a 1 where the two bits differ
    a = a ^ b;
    // 4. The carries become the second number, still to be added
    b = carry;
  }
  // 5. No carry is left, so the first number is the sum
  return a;
}

def solve(a, b):
    # Python only: a Python whole number has no fixed width, so a carry could
    # keep moving left forever. The mask, 32 ones, keeps the lowest 32 bits.
    mask = 0xFFFFFFFF
    a &= mask
    b &= mask
    # 1. Repeat while the second number is not 0
    while b != 0:
        # 2. Find the carries: a 1 where both bits are 1, moved one place left
        # Python only: "& mask" drops a carry that moves past the 32 bits.
        carry = ((a & b) << 1) & mask
        # 3. Add the columns without carrying: a 1 where the two bits differ
        a ^= b
        # 4. The carries become the second number, still to be added
        b = carry
    # 5. No carry is left, so the first number is the sum
    # Python only: above 0x7FFFFFFF (a 0 and 31 ones) the leftmost of the 32
    # bits is 1, which means a negative sum. a ^ mask flips the 32 bits and ~
    # flips every bit, so the 32 bits are unchanged with endless 1s to their
    # left: that is how Python holds the negative number.
    return a if a <= 0x7FFFFFFF else ~(a ^ mask)

Example 2, traced

Input
a = 2
b = 3

Output
5

Why it works

Each round swaps the two numbers for two others with the same sum on 32 bits: the columns added without carries, and the carries moved one place left. Carries only move left through 32 columns, so they run out and the first number is the sum. Negative numbers work: -1 is stored as 32 ones, adding 1 carries through every column, the last carry is dropped, leaving 0.

Time and space

Time O(1): at most 32 rounds, extra space O(1). JavaScript's bit operators keep only 32 places, and the Python reference cuts to 32 itself. A carry moves at least one place left every round, so the loop takes at most 32 rounds, whatever the numbers are. That is constant time: O(1). A few numbers are stored: O(1) space.

n and m are input sizes, h is a tree's height, V and E are a graph's vertices and edges. The bounds describe this reference solution.

Watch out

• Work out the carries before you change the first number. If you XOR first, the AND reads the changed number and the carries come out wrong: 2 and 3 then give -1 instead of 5.
• Python's whole numbers have no fixed width, so the JavaScript loop never ends there for -2 and 3: the carry moves left forever. Keep a, b and each carry to 32 bits with & 0xFFFFFFFF, which is 32 ones.
• In JavaScript the second number can be negative: b may start that way, and a carry that reaches the leftmost bit makes it negative. Loop while it is not 0. Testing for above 0 returns -5 for -5 and -7.

Pattern

Bit manipulation. Builds on Single Number and Reverse Bits.

Keep going