#75 · Bit Manipulation

Sum of Two Integers

Return the sum of two integers a and b without using the operators + and -.

MediumLeetCode

Bit being examined
Counted / set / result
Related bit
Cleared / carried

Speed1×step 1 / 1

Pointers

Variables

Hash map / table

Stack / queue

Foundations & data-structure selection

XOR and AND as half adder

Adding two bits gives a sum bit (their XOR) and a carry bit (their AND). So a ^ b is the sum with every carry ignored, and (a & b) << 1 is exactly the carries, placed where they must be added. Adding those two numbers is the same problem again, but the carries only move upward, so the process ends.

Memory layout

Two registers.

Operation	Cost
rounds	at most 32

Two's complement

Negative integers are stored so that the same adder works for signed and unsigned numbers: the bit patterns add identically, and a carry out of the top bit is simply dropped.

Memory layout

A 32-bit word; the top bit has weight −2³¹.

Operation	Cost
negation	~x + 1

Why it fits

Hardware adders are built from XOR and AND gates; the problem asks you to rebuild one in software.
Because XOR gives sum-without-carry and AND gives the carries, repeating the step pushes every carry to the left until none are left.
Two's complement lets the same loop handle negative numbers, if the word width is fixed (32 bits) so the carries eventually fall off the top.

Why alternatives degrade

Using ++ in a loop b times:: It breaks the spirit of the problem (increment is addition), and it is O(b), which is far too slow for large values.
Logarithm / exponent tricks:: Floating-point is inexact and the operations still contain addition.
Pointer arithmetic (&a[b]):: It is an addition in disguise and is undefined behaviour in several languages.

Four approaches, from naive to production

1 · beginner

Full adder, one bit at a time

time O(32)space O(1)

Go through the 32 bit positions from the right. At each position take the two bits and the incoming carry: the sum bit is their XOR and the carry out is 1 if at least two of the three are 1.

int getSum(int a, int b) {
    unsigned result = 0, carry = 0;
    for (int i = 0; i < 32; i++) {
        unsigned x = ((unsigned)a >> i) & 1, y = ((unsigned)b >> i) & 1;
        unsigned bit = x ^ y ^ carry;
        carry = (x & y) | (x & carry) | (y & carry);
        result |= bit << i;
    }
    return (int)result;
}

public int getSum(int a, int b) {
    int result = 0, carry = 0;
    for (int i = 0; i < 32; i++) {
        int x = (a >>> i) & 1, y = (b >>> i) & 1;
        int bit = x ^ y ^ carry;
        carry = (x & y) | (x & carry) | (y & carry);
        result |= bit << i;
    }
    return result;
}

def get_sum(a, b):
    result, carry = 0, 0
    for i in range(32):
        x, y = (a >> i) & 1, (b >> i) & 1
        bit = x ^ y ^ carry
        carry = (x & y) | (x & carry) | (y & carry)
        result |= bit << i
    return result if result < 2**31 else result - 2**32

function getSum(a: number, b: number): number {
  let result = 0, carry = 0;
  for (let i = 0; i < 32; i++) {
    const x = (a >>> i) & 1, y = (b >>> i) & 1;
    const bit = x ^ y ^ carry;
    carry = (x & y) | (x & carry) | (y & carry);
    result |= bit << i;
  }
  return result;
}

Flaws & bottlenecks

Always 32 iterations, even when the numbers are small.
More operations per step than the carry-propagation loop.
Sign handling relies on the arithmetic of the host language for the last step.

Interviewer cross-questions

Why is the sum bit x XOR y XOR carry?

Say: The sum bit is 1 exactly when an odd number of the three inputs are 1. XOR of three bits gives that.

When is there a carry out?

Say: When at least two of the three inputs are 1: (x & y) | (x & carry) | (y & carry).

How is this a real adder?

Say: It is the ripple-carry adder: a chain of 32 full adders, each passing its carry to the next.

2 · intermediate

Recursion: sum without carry, plus the carries

time O(32) calls at mostspace O(32) recursion

a + b equals (a XOR b) + ((a AND b) << 1). Replace the pair (a, b) by those two numbers and repeat until the second is 0; then the first is the answer.

int getSum(int a, int b) {
    if (b == 0) return a;
    return getSum(a ^ b, (int)((unsigned)(a & b) << 1));
}

public int getSum(int a, int b) {
    if (b == 0) return a;
    return getSum(a ^ b, (a & b) << 1);
}

def get_sum(a, b):
    MASK = 0xFFFFFFFF
    def go(x, y):
        if y == 0: return x
        return go((x ^ y) & MASK, ((x & y) << 1) & MASK)
    r = go(a & MASK, b & MASK)
    return r if r <= 0x7FFFFFFF else ~(r ^ MASK)

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

Flaws & bottlenecks

Uses recursion for a loop that is naturally iterative.
In languages without fixed-width integers (Python) it never ends for negative numbers unless values are masked.
Left-shifting a negative number is undefined behaviour in some languages (C++ before C++20).

Interviewer cross-questions

Why does the recursion terminate?

Say: Each round the carry word moves at least one position to the left. After at most 32 rounds it is shifted out of a 32-bit word and becomes 0.

Why does it not terminate in Python for negative inputs?

Say: Python integers are unbounded, so the carries never fall off the top. Masking to 32 bits restores the fixed width.

What is the identity behind it?

Say: a + b = (a ^ b) + 2 · (a & b): XOR adds without carries, and AND finds the positions that produce a carry (worth twice their position).

3 · advanced

Iterative carry propagation

time O(32)space O(1)

While b (the carry word) is not zero: compute carry = (a AND b) << 1, set a = a XOR b, and set b = carry. When b is zero, a holds the sum.

int getSum(int a, int b) {
    while (b != 0) {
        int carry = (int)((unsigned)(a & b) << 1);
        a = a ^ b;
        b = carry;
    }
    return a;
}

public int getSum(int a, int b) {
    while (b != 0) {
        int carry = (a & b) << 1;
        a = a ^ b;
        b = carry;
    }
    return a;
}

def get_sum(a, b):
    MASK = 0xFFFFFFFF
    a, b = a & MASK, b & MASK
    while b != 0:
        carry = ((a & b) << 1) & MASK
        a = (a ^ b) & MASK
        b = carry
    return a if a <= 0x7FFFFFFF else ~(a ^ MASK)

function getSum(a: number, b: number): number {
  while (b !== 0) {
    const carry = (a & b) << 1;
    a = a ^ b;
    b = carry;
  }
  return a;
}

Flaws & bottlenecks

Relies on fixed-width signed integers; with unbounded integers it can loop forever.
The left shift of a negative value is undefined behaviour in C++ (use unsigned types).
The number of rounds depends on the longest carry chain: up to 32.

Interviewer cross-questions

How many rounds can it take?

Say: At most 32 for 32-bit words: each round the highest carry moves up at least one position. For 1 + 0x7fffffff the carry ripples through every bit.

What changes for negative numbers?

Say: Nothing, in two's complement: the same bit patterns add up correctly. The only requirement is that the word has a fixed width so the final carry out of the top is dropped.

How would you subtract?

Say: Negate the second number with two's complement (~b + 1, which itself needs an add: use the same routine) and add.

4 · expert

Unsigned arithmetic with the sign restored at the end

time O(32)space O(1)

Run the loop on unsigned 32-bit values (masking after every shift or xor so nothing exceeds 32 bits), then convert the final pattern back to a signed integer. This version is portable across languages and has no undefined behaviour.

int getSum(int a, int b) {
    unsigned x = a, y = b;
    while (y != 0) {
        unsigned carry = (x & y) << 1;
        x = x ^ y;
        y = carry;
    }
    return (int)x;
}

public int getSum(int a, int b) {
    long x = a & 0xFFFFFFFFL, y = b & 0xFFFFFFFFL;
    while (y != 0) {
        long carry = ((x & y) << 1) & 0xFFFFFFFFL;
        x = (x ^ y) & 0xFFFFFFFFL;
        y = carry;
    }
    return (int) x;
}

def get_sum(a, b):
    MASK = 0xFFFFFFFF
    x, y = a & MASK, b & MASK
    while y != 0:
        carry = ((x & y) << 1) & MASK
        x = (x ^ y) & MASK
        y = carry
    return x if x <= 0x7FFFFFFF else ~(x ^ MASK)

function getSum(a: number, b: number): number {
  let x = a >>> 0, y = b >>> 0;
  while (y !== 0) {
    const carry = ((x & y) << 1) >>> 0;
    x = (x ^ y) >>> 0;
    y = carry;
  }
  return x | 0;
}

Flaws & bottlenecks

More conversions and masks to read.
The conversion back to signed differs in each language (| 0, a cast, a subtraction of 2³²).
Only handles exactly 32-bit results; overflow of the true sum is silently wrapped.

Interviewer cross-questions

Why use unsigned values?

Say: Left shifts and overflow are well defined on unsigned types in C and C++ and the masks work the same in Python and JavaScript. It avoids undefined behaviour on negative numbers.

How do you convert back to signed?

Say: If the top bit is set, the value is x − 2³². In JavaScript x | 0 does it; in Java and C++ a cast to int does.

What happens when the true sum does not fit in 32 bits?

Say: The result wraps around, exactly like int addition overflow in Java or two's complement hardware. The problem keeps the inputs small enough that it never happens.

Synchronized code walkthrough

Showing: Full adder, one bit at a time — shares the player above; click any step to jump.

int getSum(int a, int b) {
    unsigned result = 0, carry = 0;
    for (int i = 0; i < 32; i++) {
        unsigned x = ((unsigned)a >> i) & 1, y = ((unsigned)b >> i) & 1;
        unsigned bit = x ^ y ^ carry;
        carry = (x & y) | (x & carry) | (y & carry);
        result |= bit << i;
    }
    return (int)result;
}

public int getSum(int a, int b) {
    int result = 0, carry = 0;
    for (int i = 0; i < 32; i++) {
        int x = (a >>> i) & 1, y = (b >>> i) & 1;
        int bit = x ^ y ^ carry;
        carry = (x & y) | (x & carry) | (y & carry);
        result |= bit << i;
    }
    return result;
}

def get_sum(a, b):
    result, carry = 0, 0
    for i in range(32):
        x, y = (a >> i) & 1, (b >> i) & 1
        bit = x ^ y ^ carry
        carry = (x & y) | (x & carry) | (y & carry)
        result |= bit << i
    return result if result < 2**31 else result - 2**32

function getSum(a: number, b: number): number {
  let result = 0, carry = 0;
  for (let i = 0; i < 32; i++) {
    const x = (a >>> i) & 1, y = (b >>> i) & 1;
    const bit = x ^ y ^ carry;
    carry = (x & y) | (x & carry) | (y & carry);
    result |= bit << i;
  }
  return result;
}

int getSum(int a, int b) {
    if (b == 0) return a;
    return getSum(a ^ b, (int)((unsigned)(a & b) << 1));
}

public int getSum(int a, int b) {
    if (b == 0) return a;
    return getSum(a ^ b, (a & b) << 1);
}

def get_sum(a, b):
    MASK = 0xFFFFFFFF
    def go(x, y):
        if y == 0: return x
        return go((x ^ y) & MASK, ((x & y) << 1) & MASK)
    r = go(a & MASK, b & MASK)
    return r if r <= 0x7FFFFFFF else ~(r ^ MASK)

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

int getSum(int a, int b) {
    while (b != 0) {
        int carry = (int)((unsigned)(a & b) << 1);
        a = a ^ b;
        b = carry;
    }
    return a;
}

public int getSum(int a, int b) {
    while (b != 0) {
        int carry = (a & b) << 1;
        a = a ^ b;
        b = carry;
    }
    return a;
}

def get_sum(a, b):
    MASK = 0xFFFFFFFF
    a, b = a & MASK, b & MASK
    while b != 0:
        carry = ((a & b) << 1) & MASK
        a = (a ^ b) & MASK
        b = carry
    return a if a <= 0x7FFFFFFF else ~(a ^ MASK)

function getSum(a: number, b: number): number {
  while (b !== 0) {
    const carry = (a & b) << 1;
    a = a ^ b;
    b = carry;
  }
  return a;
}

int getSum(int a, int b) {
    unsigned x = a, y = b;
    while (y != 0) {
        unsigned carry = (x & y) << 1;
        x = x ^ y;
        y = carry;
    }
    return (int)x;
}

public int getSum(int a, int b) {
    long x = a & 0xFFFFFFFFL, y = b & 0xFFFFFFFFL;
    while (y != 0) {
        long carry = ((x & y) << 1) & 0xFFFFFFFFL;
        x = (x ^ y) & 0xFFFFFFFFL;
        y = carry;
    }
    return (int) x;
}

def get_sum(a, b):
    MASK = 0xFFFFFFFF
    x, y = a & MASK, b & MASK
    while y != 0:
        carry = ((x & y) << 1) & MASK
        x = (x ^ y) & MASK
        y = carry
    return x if x <= 0x7FFFFFFF else ~(x ^ MASK)

function getSum(a: number, b: number): number {
  let x = a >>> 0, y = b >>> 0;
  while (y !== 0) {
    const carry = ((x & y) << 1) >>> 0;
    x = (x ^ y) >>> 0;
    y = carry;
  }
  return x | 0;
}