#371 Sum of Two Integers

Mediumsolve on LeetCode ↗

frequently reported atGoogle Amazon Meta Microsoft

the problem

In plain words

Return a + b without using the operators + and −.

in a = 1, b = 2

out 3

in a = 2, b = 3

out 5

−1000 ≤ a, b ≤ 1000

your turn

Try it before you peek

Read the examples, say the brute force out loud, then write code: here or on LeetCode ↗. Stuck for 20 minutes? Open one hint at a time.

Solve it in the browser

LeetCode-style: complete the class. Compiled by the real javac (Java 17) and judged right here — nothing is sent anywhere.

Solutions are hidden so you can try first. Even 20 minutes of real effort makes the answer stick far better than reading it.

Marking the problem solved, or opening every hint, also shows it.

the aha

Key insight

patternBit tricks (shift, mask, lowest set bit)

Binary addition has two parts. The column sum without carry is a ^ b, and the carries are (a & b) << 1. Keep adding the carries until there are none.

solutions

From brute force to optimal

Simulate a hardware full adder for each of the 32 columns.

For i in 0..31: take bit i of a and b.
sum bit = x ^ y ^ carry, new carry = majority(x, y, carry).
Write the sum bit into result.

timeO(32) = O(1)

Always 32 columns.

spaceO(1)

A few ints.

java

1class Solution {2    public int getSum(int a, int b) {3        int result = 0, carry = 0;4        for (int i = 0; i < 32; i++) {5            int x = (a >>> i) & 1, y = (b >>> i) & 1;6            int sum = x ^ y ^ carry;                     // 1 when an odd number of 1s7            carry = (x & y) | (x & carry) | (y & carry); // 1 when at least two 1s8            result |= sum << i;9        }10        return result;11    }12}

a ^ b adds without carrying; (a & b) << 1 is what still needs adding. Repeat until no carry.

While b ≠ 0: carry = (a & b) << 1; a = a ^ b; b = carry.
Return a.

timeO(32) = O(1)

Each round moves the lowest carry at least one place left, so there are at most 32 rounds before it falls off the top.

spaceO(1)

One temp variable.

java

1class Solution {2    public int getSum(int a, int b) {3        while (b != 0) {4            int carry = (a & b) << 1; // where both are 1, a carry moves left5            a = a ^ b; // add without carrying6            b = carry; // now add the carries7        }8        return a;9    }10}

sim

Dry run

loading simulation…

java

1class Solution {2    public int getSum(int a, int b) {3        while (b != 0) {4            int carry = (a & b) << 1; // where both are 1, a carry moves left5            a = a ^ b; // add without carrying6            b = carry; // now add the carries7        }8        return a;9    }10}

in the room

How to say it in the interview

talk track

Do 5 + 3 in binary on the whiteboard: 101 ^ 011 = 110 and (101 & 011) << 1 = 010, then 110 ^ 010 = 100 and the carry is 100. One more round: 100 ^ 100 = 000 with carry 1000, which gives 1000 = 8.
Mention that in Java negatives just work, because int arithmetic wraps in two's complement. In Python you'd need a 32-bit mask.

traps

Computing the carry after overwriting a. Save (a & b) << 1 first.

what they ask next

Follow-ups

Subtraction without −?

a − b = a + (~b + 1). Reuse the same adder.

before you submit

Edge cases to test

−1 + 1 → 0: the carry runs off the top and disappears (Java ints wrap).
Both negative (−5 + −7): two's complement needs no special case.
511 + 1: a long carry chain, still at most 32 rounds.

practise next