Skip to main content

371. Sum of Two Integers

medium

Add two integers without using the + or - operators. Implement addition from first principles using XOR for partial-sum bits and AND-shift for carry bits.

By Sam K., Founder, InterviewChamp.AI · Last verified

Problem

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

Constraints

  • -1000 <= a, b <= 1000

Examples

Example 1

Input
a = 1, b = 2
Output
3

Example 2

Input
a = 2, b = 3
Output
5

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

Imagine adding two binary numbers by hand. At each position you get a partial-sum bit and a carry bit.

Hint 2

Partial sum without carry: a XOR b. Carry: (a AND b) << 1.

Hint 3

Loop: while b (the carry) is nonzero, set a = a XOR b and b = (a AND b) << 1. Eventually carry becomes 0 and a holds the answer.

Hint 4

Watch out for signed integer overflow in fixed-width languages. Mask with 0xFFFFFFFF and handle negatives explicitly in Python.

Solution approach

Reveal approach

Loop until no carry. In each iteration, partial_sum = a ^ b (adds each bit position ignoring carry), carry = (a & b) << 1 (a bit at position i in both a and b carries into position i+1). Set a = partial_sum, b = carry, and repeat. When b = 0 there's no more carry and a is the sum. In Python (arbitrary precision ints), mask both with 0xFFFFFFFF inside the loop and interpret a > 0x7FFFFFFF as the negative two's-complement value before returning. In C/Java/Go the native 32-bit semantics handle wraparound automatically. O(log max) iterations because each loop pushes the carry one bit higher. O(1) space.

Complexity

Time
O(1) — bounded by bit width
Space
O(1)

Related patterns

  • bit-manipulation

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Amazon
  • Microsoft
  • Google
  • Apple

More Bit Manipulation practice problems

See all Bit Manipulation problems →