☕ DSA Java Articles

Topics › Bit Manipulation › Interview Problems

Sum of Two Integers

Easy TUF ID 2411 Blind 75

LeetCode ↗ Java source ↗ Edit this article ↗

Problem

Given two integers a and b, return a + b without using the + or - operators. Bitwise operators (&, |, ^, ~), shifts and comparisons are allowed. The exercise is really “rebuild addition out of the logic gates that a CPU’s adder is made of”.

Constraints: -1000 ≤ a, b ≤ 1000 on LeetCode. The methods below work for every pair of 32-bit int values and, exactly like Java’s own +, wrap around on overflow: Integer.MAX_VALUE plus 1 gives Integer.MIN_VALUE.

Example 1

a = 1, b = 2
answer = 3          // 01 + 10 = 11, no column produces a carry

Example 2

a = -1, b = 1
answer = 0          // 111...111 + 000...001: a carry ripples through all 32 bits and falls off the top

Background: what addition looks like in binary

Add two binary numbers the way you add decimal ones on paper: column by column from the right, carrying into the next column. In base 2 a column has three inputs, the bit x of a, the bit y of b, and the carry c coming in from the right, and two outputs:

Ignore the incoming carry for a moment and look at the two-input case: 0+0 = 0, 0+1 = 1, 1+1 = 10. The sum bit is x ^ y and the carry is x & y. XOR is “addition without carrying” and AND is “where does a carry happen”. Both approaches below are built on that one observation.

Negative numbers need no special case. Java stores int in two’s complement, and the whole reason hardware uses two’s complement is that the same unsigned adder produces correct signed results: add the bit patterns, throw away any carry out of bit 31, and the remaining 32 bits are the right answer. -1 is all ones; adding 1 turns every bit to 0 and pushes a carry out of the top, which is discarded, leaving 0.

Approach 1: Brute force, a bit-by-bit ripple-carry adder

Intuition. Simulate the paper method literally. Walk from bit 0 to bit 31, read one bit of each operand, produce the sum bit with the full-adder formula, and pass the carry to the next position. A loop counter i++ would itself use +, so instead we walk a one-bit mask leftwards with mask <<= 1. After bit 31 the 1 is shifted out, the mask becomes 0, and the loop ends after exactly 32 rounds.

Algorithm.

  1. Start with result = 0 and carry = 0.
  2. For each mask in 1, 2, 4, ... until it becomes 0:
    • read x and y, the bits of a and b at that position;
    • if x ^ y ^ carry is 1, set that bit in result;
    • update carry = (x & y) | (carry & (x ^ y)).
  3. Return result. The carry left after bit 31 is dropped, which is exactly 32-bit wrap-around.
static int rippleCarry(int a, int b) {
    int result = 0, carry = 0;
    for (int mask = 1; mask != 0; mask <<= 1) {   // 32 rounds: after bit 31 the 1 falls off the top
        int x = (a & mask) != 0 ? 1 : 0;
        int y = (b & mask) != 0 ? 1 : 0;
        if ((x ^ y ^ carry) == 1) result |= mask;  // sum bit of a full adder
        carry = (x & y) | (carry & (x ^ y));       // carry into the next position
    }
    return result;
}

Complexity. Time O(32), which is O(1): one round per bit position whatever the inputs. Space O(1).

It always pays for all 32 columns, even for 1 + 2, and each round does several operations. It is the “obviously correct” baseline that the next approach compresses.

Approach 2: Optimal, XOR for the sum and AND-shift for the carries

Intuition. Do every column at once. a ^ b is the sum of all columns with carries ignored. a & b marks the columns where both bits are 1, which are exactly the columns that generate a carry, and a carry lands one column to the left, so the carries form the number (a & b) << 1. That gives the identity

a + b == (a ^ b) + ((a & b) << 1)

We have replaced one addition with another, so it looks circular. The progress is in the second operand: if b has t trailing zeros, then a & b has at least t (AND can only clear bits) and the shifted carry has at least t + 1. Each round pushes the carry at least one position left, so after at most 32 rounds the carry has shifted out of the int and becomes 0. At that point the first operand is the answer.

Algorithm.

  1. While b != 0:
    • carry = (a & b) << 1;
    • a = a ^ b;
    • b = carry.
  2. Return a.
static int optimal(int a, int b) {
    while (b != 0) {
        int carry = (a & b) << 1;   // where both bits are 1, a carry moves one position left
        a = a ^ b;                  // add every position, ignoring carries
        b = carry;                  // the carries still have to be added
    }
    return a;
}

Dry run on a = 5, b = 3, showing the low 4 bits:

round a b a ^ b (a & b) « 1
1 0101 0011 0110 0010
2 0110 0010 0100 0100
3 0100 0100 0000 1000
4 0000 1000 1000 0000

b is now 0 and a = 1000, which is 8. Each round is one more step of the same carry chain, so the number of rounds is one more than the longest run of carries. -1 + 1 is the worst case: the carry walks through all 32 positions before it leaves the word.

Complexity. Time O(32) in the worst case and usually far fewer rounds. Space O(1).

Approach 3: The same identity, written recursively

Intuition. The identity a + b == (a ^ b) + ((a & b) << 1) reads naturally as a recursive definition, with b == 0 as the base case because adding zero changes nothing. The termination argument is the same as before: the second argument gains a trailing zero on every call.

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

Complexity. Time O(32). Space O(32) for the call stack, which is why the loop version is preferred, although 32 frames is harmless.

Follow-up: subtraction

In two’s complement, -b == ~b + 1: flipping every bit of b gives -b - 1. So a - b is two of our additions and no - operator:

static int subtract(int a, int b) {
    return optimal(a, optimal(~b, 1));
}

Edge cases and pitfalls