Log inSign up
mediumLeetCodeNot Started

Sum of Two Integers

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Bit Manipulation
Solve on LeetCode
Lesson

Problem Statement

Given two integers a and b, return the sum of the two integers without using the operators + and -.

Example 1 · Example 1: Positive Addition:

Input: a = 1, b = 2
Output: 3
Explanation: 1 + 2 = 3. 01_2 ^ 10_2 = 11_2 (3), with 0 carry.

Example 2 · Example 2: Negative Addition:

Input: a = 2, b = 3
Output: 5
Explanation: 2 (010) + 3 (011) = 5 (101).

Example 3 · Example 3: Mixed Signs:

Input: a = -2, b = 3
Output: 1
Explanation: -2 + 3 = 1.

Constraints:

  • -1000 <= a, b <= 1000

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Understand half-adder and full-adder digital logic in software.
  • Simulate carry propagation using bitwise AND and left-shift.
  • Safely handle two's complement signed negative numbers in dynamically typed languages.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Sum without using arithmetic operators + or -.
  • Binary circuit addition simulation.
  • Bit-level carry propagation.

Algorithmic Decision Tree:

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

Connected Patterns:

Divide Two Integers Without OperatorsSquare of a Number Without MultiplicationSingle Number

1. Bit-by-Bit Full Adder Simulation

Intuition

Initialize carry = 0, res = 0. For i from 0 to 31, extract bitA = (a >> i) & 1, bitB = (b >> i) & 1. Compute sumBit = bitA ^ bitB ^ carry, and update carry = (bitA & bitB) | (carry & (bitA ^ bitB)). Set bit i in res.

When to apply: When understanding gate-level computer architecture.

Algorithm

  1. Step 1: Set res = 0, carry = 0.
  2. Step 2: Loop i from 0 to 31.
  3. Step 3: Extract bitA, bitB.
  4. Step 4: sumBit = bitA ^ bitB ^ carry.
  5. Step 5: carry = (bitA & bitB) | (carry & (bitA ^ bitB)).
  6. Step 6: res |= (sumBit << i). Return res.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2
3using namespace std;
4
5int getSumFullAdder(int a, int b) {
6 int res = 0;
7 int carry = 0;
8 for (int i = 0; i < 32; ++i) {
9 int bitA = (a >> i) & 1;
10 int bitB = (b >> i) & 1;
11 int sumBit = bitA ^ bitB ^ carry;
12 carry = (bitA & bitB) | (carry & (bitA ^ bitB));
13 res |= (sumBit << i);
14 }
15 return res;
16}
17
18int main() {
19 cout << "Full Adder (1, 2): " << getSumFullAdder(1, 2) << endl; // 3
20 cout << "Full Adder (2, 3): " << getSumFullAdder(2, 3) << endl; // 5
21 cout << "Full Adder (-2, 3): " << getSumFullAdder(-2, 3) << endl; // 1
22 return 0;
23}

Time & Space Complexity

  • Time complexity: O(32) = O(1)
  • Space complexity: O(1)

2. Recursive Half Adder

Intuition

Base case: if carry b == 0, return a. Otherwise, compute partial sum a ^ b and carry (a & b) << 1, and recurse.

When to apply: Compact functional implementation.

Algorithm

  1. Step 1: If b == 0, return a.
  2. Step 2: Return getSum(a ^ b, (unsigned)(a & b) << 1).
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2
3using namespace std;
4
5int getSumRecursive(int a, int b) {
6 if (b == 0) return a;
7 return getSumRecursive(a ^ b, (unsigned int)(a & b) << 1);
8}
9
10int main() {
11 cout << "Recursive (1, 2): " << getSumRecursive(1, 2) << endl; // 3
12 cout << "Recursive (2, 3): " << getSumRecursive(2, 3) << endl; // 5
13 cout << "Recursive (-2, 3): " << getSumRecursive(-2, 3) << endl; // 1
14 return 0;
15}

Time & Space Complexity

  • Time complexity: O(1) (<= 32 recursive calls)
  • Space complexity: O(32) recursion stack

3. Iterative Half-Adder Circuit

Intuition

In an iterative while loop until carry b == 0: calculate carry vector (a & b) << 1, update a = a ^ b, and set b = carry. Handles negative integers and 32-bit limits cleanly.

When to apply: Optimal canonical solution for Sum of Two Integers.

Algorithm

  1. Step 1: While b != 0:
  2. Step 2: carry = (unsigned)(a & b) << 1.
  3. Step 3: a = a ^ b.
  4. Step 4: b = carry.
  5. Step 5: Return a.

Half-Adder Circuit Trace: a = 2 (010_2), b = 3 (011_2)

2 of 2 questions left today
Step 1 / 2
Trace timeline50% explored
Current operationSTEP 1 OF 2
Pass 1: a = 2 (010_2), b = 3 (011_2)
Visual state
Values and pointers at this exact step
pointers
S
1
4
0
↑ sum
1
↑ carry
Check / comparison
carry = 4 != 0
Decision / next transition
Next iteration with a = 1, b = 4.
Why this step matters

Pass 1: a = 2 (010_2), b = 3 (011_2). carry = (2 & 3) << 1 = 2 << 1 = 4 (100_2). sum = 2 ^ 3 = 1 (001_2). a becomes 1, b becomes 4.

Step 1 / 2
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2
3using namespace std;
4
5class Solution {
6public:
7 int getSum(int a, int b) {
8 while (b != 0) {
9 unsigned int carry = (unsigned int)(a & b) << 1;
10 a = a ^ b;
11 b = carry;
12 }
13 return a;
14 }
15};
16
17int main() {
18 Solution sol;
19 cout << "Optimal (1, 2): " << sol.getSum(1, 2) << endl; // 3
20 cout << "Optimal (2, 3): " << sol.getSum(2, 3) << endl; // 5
21 cout << "Optimal (-2, 3): " << sol.getSum(-2, 3) << endl; // 1
22 return 0;
23}

Time & Space Complexity

  • Time complexity: O(1) (at most 32 loops)
  • Space complexity: O(1)

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Brute Force — Bit-by-Bit Full Adder SimulationO(32) = O(1)O(1)Simulate a 32-bit hardware full adder by tracking carry bit-by-bit from index 0 to 31.Fixed 32 bit loop.
2.Better — Recursive Half AdderO(1) (<= 32 calls)O(32) call stackb == 0 ? a : getSum(a ^ b, (unsigned)(a & b) << 1).Call stack recursion.
3.Optimal — Iterative Half-Adder CircuitOptimalO(1) (at most 32 loops)O(1)While b != 0: carry = (unsigned)(a & b) << 1; a = a ^ b; b = carry; return a.Carry propagation loop.

Common Pitfalls & Crucial Edge Cases

Using `+` or `-` operators

The problem forbids the addition operator.

Python infinite loop

Forgetting the & 0xFFFFFFFF mask in Python causes infinite loops on negative numbers.

Signed left shift overflow in C++

(a & b) << 1 on signed int can trigger undefined behavior if the carry shifts into the sign bit. Cast to unsigned int before shifting.

Crucial Edge Cases to Validate:

  • One or both numbers are 0 — a + 0 = a.
  • Opposite signs canceling to 0 (e.g. a = 5, b = -5) — Returns 0.
  • Two negative numbers (e.g. a = -3, b = -4) — Returns -7.
  • Python arbitrary precision — Must apply 32-bit mask mask = 0xFFFFFFFF to avoid infinite loops.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Draw the digital logic half-adder diagram: sum = a ^ b, carry = (a & b) << 1.
  2. Highlight how subtraction is inherently supported through two's complement arithmetic without needing separate code.
  3. Discuss language-specific quirks: C++ signed overflow avoidance and Python's arbitrary-precision masking.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.Why does bitwise XOR compute the sum of two integers without carries?

2.When does the iterative sum loop while (b != 0) terminate?

3.How does Python handle negative numbers during bitwise addition?

Back to DSA Sheet