Sum of Two Integers

The problem

You are given two whole numbers first and second. Return first + second, but without using the + or − operators anywhere in your code.

Example 1

Input: first = 13, second = 11

Output: 24

In binary, 1101 plus 1011 is 11000. The picture shows the low 8 bits of each.

first = 13

00001101

second = 11

00001011

sum = 24

00011000

Example 2

Input: first = -5, second = 3

Output: -2

Negative numbers work too, because they are stored as 32-bit two’s complement.

Example 3

Input: first = 0, second = 7

Output: 7

Adding 0 changes nothing. The carry loop stops after one run.

Constraints

• −1,000 ≤ first, second ≤ 1,000
• Below, b also stands for the number of bits (32) inside O(b).

Clarifying questions

Can a or b be negative?

Yes. Numbers are 32-bit two's complement, and the same bit rules add them. Python has no fixed width, so it needs a mask.

Can we use sum(), or add 1 at a time with ++?

No. The sum itself must come from bit operators: &, |, ^ and shifts. A loop counter is fine.

Can the result overflow?

No. Both numbers are at most 1,000 in size, so the sum fits easily in 32 bits.

Spot the pattern

We cannot use +, so we must build addition from bit operators. In one column, first_bit ^ second_bit is the sum bit and first_bit & second_bit is the carry. That is bit manipulation.

Solutions

Bit by bitO(b)Carry loopO(b)

Show all

This problem has two approaches. Both are O(b) in the worst case, but the carry loop usually stops much sooner.

Bit by bit O(b)

The idea

Do what you would do on paper. Go through the 32 bit columns from right to left. In column i, take bit first_bit of first, bit second_bit of second and the carry from the column before:

• The result bit is first_bit ^ second_bit ^ carry: it is 1 when an odd number of the three are 1.
• The new carry is 1 when at least two of the three are 1: (first_bit & second_bit) | (carry & (first_bit ^ second_bit)).

Negative numbers need nothing special, because two’s complement adds the same way. Any carry out of column 31 is dropped, just as the hardware drops it.

Walkthrough

first

00001101

second

00001011

result

00000000

carry

0

1. result, carry = 0, 0
2. for i in range(32):
3. first_bit, second_bit = (first >> i) & 1, (second >> i) & 1
4. result |= (first_bit ^ second_bit ^ carry) << i
5. carry = (first_bit & second_bit) | (carry & (first_bit ^ second_bit))
6. return result

first = 13 and second = 11. Add them the way you add by hand, one bit column at a time from the right, keeping a carry. Do it for all 32 columns.

← BackStep →Play1 / 11

Code

JSolution.javaPysolution.pyC#Solution.csGosolution.goTSsolution.ts

JavaPythonC#GoTypeScript

JavaPythonC#GoTypeScript

class Solution {
    // Bit by bit: add the 32 columns from right to left, keeping a carry.
    // Always 32 runs: O(b) time, O(1) memory.
    public int getSum(int first, int second) {
        int result = 0, carry = 0;
        for (int i = 0; i < 32; i++) {
            int firstBit = (first >> i) & 1, secondBit = (second >> i) & 1;
            // The result bit is 1 when an odd number of firstBit, secondBit, carry are 1.
            result |= (firstBit ^ secondBit ^ carry) << i;
            // The carry is 1 when at least two of them are 1.
            carry = (firstBit & secondBit) | (carry & (firstBit ^ secondBit));
        }
        return result;
    }
}

Big O

Time O(b)Space O(1)Here is how we get these from the code, in four steps.

1. 1 Find the work that repeats

   The lit lines read two bits, write one bit and work out the carry. That is 1 step. They sit inside one loop.

   1. result, carry = 0, 0
   2. for i in range(32):
   3. first_bit, second_bit = (first >> i) & 1, (second >> i) & 1
   4. result |= (first_bit ^ second_bit ^ carry) << i
   5. carry = (first_bit & second_bit) | (carry & (first_bit ^ second_bit))
   6. return result

2. 2 Count the runs on Example 1

   The loop runs once per column. The table groups the columns by byte.

   8 + 8 + 8 + 8 = 32 runs.

   columns	0–7	8–15	16–23	24–31
   runs	8	8	8	8

   total

   8 + 8 + 8 + 8 = 32 runs

3. 3 Write the count for any n

   The loop always runs once per bit, whatever the numbers are:

   b runs, and b = 32

   Check it with Example 3: adding 0 still takes 32 runs.

4. 4 Keep only the part that grows fastest

   There is nothing to drop. The count is b. Since b is fixed at 32, you can also call it O(1).

   So the time is O(b).

5. S Space: count the extra memory the same way

   The code keeps result, carry, first_bit, second_bit and i. The space is O(1).

   resultcarryfirst_bitsecond_biti

Carry loop O(b)

The idea

Do all 32 columns at once, and handle the carries afterward:

• first ^ second adds every column but ignores the carries.
• first & second marks the columns where both bits are 1. Each one makes a carry, and << 1 moves the carries into the next column.

So first + second equals (first ^ second) + ((first & second) << 1). That is still an addition, so repeat the same trick on those two numbers. Stop when the carry is 0, because then first ^ second is the whole sum.

Walkthrough

first

00001101

second

00001011

1. while second != 0:
2. carry = (first & second) << 1
3. first = first ^ second
4. second = carry
5. return first

first ^ second adds every column but drops the carries. (first & second) << 1 is exactly those carries, moved one column left. So first + second = (first ^ second) + ((first & second) << 1). Repeat until there is no carry.

← BackStep →Play1 / 10

Code

JSolution.javaPysolution.pyC#Solution.csGosolution.goTSsolution.ts

JavaPythonC#GoTypeScript

JavaPythonC#GoTypeScript

class Solution {
    // Carry loop: first ^ second is the sum without carries, (first & second) << 1 is the carries.
    // One run per step of the longest carry chain, at most 32: O(b) time, O(1) memory.
    public int getSum(int first, int second) {
        while (second != 0) {
            int carry = (first & second) << 1;
            first = first ^ second;
            second = carry;
        }
        return first;
    }
}

Big O

Time O(b)Space O(1)Here is how we get these from the code, in four steps.

1. 1 Find the work that repeats

   The lit lines do one &, one shift and one ^ on whole 32-bit words. That is 1 step. They sit inside one loop.

   1. while second != 0:
   2. carry = (first & second) << 1
   3. first = first ^ second
   4. second = carry
   5. return first

2. 2 Count the runs on Example 1

   Example 1 adds 13 and 11. The table shows first and the carry second after each run.

   4 runs, against 32 for the bit-by-bit adder.

   run	1	2	3	4
   first after	6	20	16	24
   second (carry) after	18	4	8	0

   total

   4 runs

3. 3 Write the count for any n

   Each run moves every carry one column to the left. A carry either dies out or slides off the top after at most b moves:

   at most b runs, and b = 32

   Check it with Example 3: 0 & 7 = 0, so 1 run. The worst case is a carry that ripples through every column, like −1 + 1, which takes 32 runs.

4. 4 Keep only the part that grows fastest

   There is nothing to drop. The worst case is b, the same as the first approach. But the count follows the longest carry chain, which is short for most numbers.

   So the time is O(b).

5. S Space: count the extra memory the same way

   The code keeps only carry, besides first and second. The space is O(1).

   carry

Common mistake

An endless loop in Python

Python numbers have no 32-bit limit. For −1 + 1, the carry keeps moving left forever and never drops off the top. Mask first, second and the carry with 0xFFFFFFFF to keep 32 bits, and turn a result above 0x7FFFFFFF back into a negative number at the end.

Tested at the limits

2,000 random pairs from −1,000 to 1,000, with signs mixed on purpose. Bit by bit and the carry loop gave the same answer every time, and matched plain addition.

Largest inputs	Result
−1 + 1, where the carry runs through all 32 bits, the most loops. Carry loop.	Under 0.001 s, and under 0.001 MB of extra memory: just carry, first and second.
All 256 pairs of 16 edge values, such as −1,000, −513, 0, 255 and 1,000. Both approaches.	Every sum was right.