Frontend Beauty
ESC

Type to search the knowledge base.

Sum of Two Integers

Add without + or − operators — XOR for sum bits, AND+shift for carry, loop until carry clears.

intermediate3 min read
  • dsa
  • bit
  • interview
  • Google
  • Meta
  • Amazon

The problem

Given integers a and b, return their sum without using the + or - operators.

Input:  a = 1, b = 2
Output: 3

Input:  a = 2, b = 3
Output: 5

Brute force (not bit math)

Loop increment — banned in spirit, and awkward for negatives.

Optimal: XOR + carry

  • a ^ b — sum without carry
  • (a & b) << 1 — carry bits
  • Repeat until carry is 0

In languages with fixed 32-bit ints this is natural. JS numbers are IEEE doubles but bitwise ops use 32-bit signed integers — so mask with >>> 0 carefully for unsigned interpretation, and for LC-style 32-bit:

function getSum(a: number, b: number): number {
  while (b !== 0) {
    const carry = (a & b) << 1;
    a = a ^ b;
    b = carry;
  }
  return a;
}
Time O(1) — bounded by bit width (≤ 32 iterations)
Space O(1)

Why it works

Half-adder logic: sum bit is XOR, carry is AND shifted. Full addition is ripple of that.

Recursive form

function getSumRec(a: number, b: number): number {
  if (b === 0) return a;
  return getSumRec(a ^ b, (a & b) << 1);
}

Edge cases

  • Negatives — two’s complement; JS 32-bit ops handle them if you stay in 32-bit land
  • b = 0 early exit
  • Overflow beyond 32-bit — problem usually fits 32-bit
  • a = -1, b = 1 → 0

Common bugs

  • Using + accidentally in helpers
  • Infinite loop if carry shift not applied
  • Confusing JS >>> vs << on sign bit (still works for standard LC tests with the loop above)

Interview delivery

  1. No +/− → bit ops.
  2. XOR sum, AND carry.
  3. Loop.
  4. Trace 2+3:
    • 10 ^ 11 = 01, carry 100
    • 01 ^ 100 = 101, carry 0 → 5
  5. Mention half-adder.

Full trace a=5 (101), b=3 (011)

  1. carry = (101 & 011)<<1 = 010<<1 = 100; a = 101^011 = 110; b = 100
  2. carry = (110 & 100)<<1 = 100<<1 = 1000; a = 010; b = 1000
  3. carry = 0; a = 010^1000 = 1010 → 10

Negatives in two’s complement

Bitwise algorithms still work on fixed-width two’s complement addition. JS bitwise ops convert to Int32. LC constraints keep results in 32-bit range; you usually don’t need BigInt.

What not to do

  • eval hacks
  • Array of length a filled and length b — only works for non-negatives and wastes memory
  • Log/exp tricks — precision landmines

Bit addition is the point of the problem.

Further reading