Faangprep Logo
Log inStart free
Browse curriculum

Sum of Two Integers

Add two integers without the + or - operators: XOR adds without carrying, and AND shifted left is the carry.

MediumSolve on LeetCode

Problem Understanding

Sum of Two Integers: given two integers a and b, return their sum without using the + or - operators.

Examples: a = 1, b = 2 returns 3; a = 2, b = 3 returns 5.

The Intuition: Split Addition Into Sum and Carry

Binary addition does two things in every column: it writes a digit and it may carry one to the left. Bitwise operators can do each part separately:

  • a ^ b writes every column's digit and ignores the carries.
  • a & b marks the columns that carry (both bits are 1), and << 1 moves those carries one column left.

Adding the carry to the carry-less sum is the same problem again, with a new a and b. Each round pushes the carries further left, so they eventually run out, and the loop stops when b, the carry, is 0.

Interactive Walkthrough

Each round shows a, b, their XOR and their carry, bit 0 on the right. Columns where both a and b are 1 are marked: those are the carries, and they reappear one column left in the carry row, which becomes the next round's b.

Dry Run Table

Input: a = 2, b = 3

Round a b a ^ b (a & b) << 1
1 010 011 001 100
2 001 100 101 000

The carry is 0 after round 2, so the answer is 101 = 5.

The Solution Template

Repeat XOR for the sum and AND-shift for the carry until the carry is zero.

Sum of Two Integers Code
1var getSum = function(a, b) {
2    while (b !== 0) {
3        const carry = (a & b) << 1;
4        a ^= b;
5        b = carry;
6    }
7    return a;
8};

Edge Cases & Common Mistakes

  • Negative numbers: two's complement makes the same loop correct in fixed-width languages; the carry eventually shifts out of bit 31.
  • Python: without the 32-bit mask, a negative carry never shifts out and the loop never ends.
  • C and C++: left-shifting a negative signed value is undefined behaviour in older standards, so shift as unsigned.
  • Updating a before computing the carry: compute (a & b) << 1 from the old a, then XOR.

Summary

Addition is a carry-less sum plus a carry. a ^ b is the first, (a & b) << 1 the second; repeat with those two as the new inputs until the carry is 0. At most 32 rounds for 32-bit integers.

More practice: DSA interview questions with answers · patterns cheat sheet

Previous

Reverse Bits

Next

Pow(x, n)

The approach, step by step

  1. Add without carrying

    Compute a ^ b, the sum of every column with the carries dropped.

  2. Compute the carry

    Compute (a & b) << 1, the carries moved one column left.

  3. Repeat until no carry

    Set a to the carry-less sum and b to the carry. When b is 0, a is the answer.

Frequently asked questions

Why does a ^ b add without carrying?

In each column, 0 + 0 = 0, 0 + 1 = 1 and 1 + 0 = 1, which is XOR. The only difference from real addition is 1 + 1, which should give 0 with a carry; XOR gives the 0 and drops the carry.

Why is the carry (a & b) << 1?

A column carries exactly when both bits are 1, which is a & b. The carry belongs one column to the left, so shift it left by one. Adding it to the carry-less sum is the same problem again, so the loop repeats until there is no carry.

Why does the Python version need a mask?

Python integers are unbounded, so a negative number has infinitely many leading 1 bits and the carry never shifts out; the loop would not end. Masking to 32 bits simulates fixed-width arithmetic, and the last line converts a result with bit 31 set back to a negative Python integer.

Applying for software engineering roles? Free, no sign-up:

AI resume checker — match your resume to the job description