Sum of Two Integers

Sum of Two Integers has a strange rule. Add two numbers, but you cannot use the plus sign. At first that feels impossible. But it forces you to think about what addition really is at the bit level. Once you see it, you understand how a computer actually adds.

🎯 The Problem

You get two numbers, a and b. You return their sum, but only with bit operations. The leftover bit that moves up to the next column is called the carry.

The rules:

• Return the sum of a and b.
• You cannot use the + operator.
• You cannot use the - operator either.
• Use bit operations only.

Let us say a is 2 and b is 3. The sum is 5. We just cannot reach it with a plain plus sign. We have to build the addition from bits.

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

Explanation: 2 + 3 = 5, found using only bit operations, no + sign.

So the goal is normal addition. The challenge is the tool we are allowed to use.

Here is how grade-school addition works, which is the same idea we copy with bits. Add the columns, and carry the overflow.

🐢 Approach 1: Count Up One At A Time (Brute Force)

The idea in one line: start at a and step up b times.

The idea:

• Begin with the value a.
• Increase it by one, b times in a row.

Why it is weak:

• Stepping up by one still uses + in spirit.
• It is painfully slow for big numbers.
• A b of two billion means two billion steps.
• So we need a real bit-based method instead.

Here is the repeated-increment code:

def get_sum(a, b):
    if b > 0:
        for _ in range(b):
            a += 1
    else:
        for _ in range(-b):
            a -= 1
    return a

⚡ Approach 2: XOR for Sum, AND for Carry (Best)

The idea in one line: split addition into a no-carry sum and a carry, then loop until the carry is gone.

The idea:

• One part is the sum without any carry.
• The other part is the carry itself.
• Each part comes from a bit operation.

How the sum works:

• The no-carry sum comes from XOR.
• Look at one column. 0 + 0 is 0. 1 + 0 is 1. 0 + 1 is 1. 1 + 1 is 0 with a carry.
• XOR gives exactly those first three results.

How the carry works:

• AND gives 1 only when both bits are 1.
• A carry is born only when both bits in a column are 1.
• So a & b marks every carry, then we shift it left by one.

How it loops:

• Set the new a to the XOR result.
• Set the new b to the shifted carry.
• Repeat until the carry becomes 0.
• This is exactly how a computer’s adder circuit works.

Here is a picture of one round of the loop. XOR makes the partial sum, AND and shift make the carry, then we loop.

Steps to Solve

1. While b is not 0, do the next steps.
2. Compute the carry as (a & b) shifted left by one.
3. Compute the partial sum as a ^ b, which is addition without carry.
4. Set a to the partial sum.
5. Set b to the carry, so the next round folds it in.
6. When b reaches 0, return a.

#include <stdio.h>

int getSum(int a, int b) {
    while (b != 0) {
        unsigned int carry = (unsigned int)(a & b) << 1; // where carries go
        a = a ^ b;                                        // add without carry
        b = (int)carry;                                   // fold carry next round
    }
    return a;
}

int main(void) {
    printf("%d\n", getSum(2, 3));
    return 0;
}

5

#include <iostream>
using namespace std;

int getSum(int a, int b) {
    while (b != 0) {
        unsigned int carry = (unsigned int)(a & b) << 1; // where carries go
        a = a ^ b;                                        // add without carry
        b = (int)carry;                                   // fold carry next round
    }
    return a;
}

int main() {
    cout << getSum(2, 3) << endl;
    return 0;
}

5

public class SumTwoIntegers {
    public static int getSum(int a, int b) {
        while (b != 0) {
            int carry = (a & b) << 1;  // where carries go
            a = a ^ b;                 // add without carry
            b = carry;                 // fold carry next round
        }
        return a;
    }

    public static void main(String[] args) {
        System.out.println(getSum(2, 3));
    }
}

5

def get_sum(a, b):
    mask = 0xFFFFFFFF          # keep only 32 bits
    while b & mask != 0:
        carry = (a & b) << 1   # where carries go
        a = a ^ b              # add without carry
        b = carry
    a = a & mask
    # handle negative results in 32-bit form
    return a if a <= 0x7FFFFFFF else ~(a ^ mask)


print(get_sum(2, 3))

5

function getSum(a, b) {
  while (b !== 0) {
    const carry = (a & b) << 1; // where carries go
    a = a ^ b; // add without carry
    b = carry; // fold carry next round
  }
  return a;
}

console.log(getSum(2, 3));

5

Let us read the core of the Python version line by line and see why it adds correctly.

while b & mask != 0:
    carry = (a & b) << 1
    a = a ^ b
    b = carry

The line while b & mask != 0: keeps the loop going while there is still a carry to add. The & mask keeps us inside 32 bits, because Python numbers can grow forever and we want true 32-bit behavior. When b has no bits left, the carry is gone and we are done.

The line carry = (a & b) << 1 finds the carry. The a & b marks every column where both bits are 1, which is exactly where a carry is born. The << 1 shifts it left by one, because a carry always moves into the next higher column.

The line a = a ^ b adds the two numbers column by column while ignoring the carry. XOR gives the right answer for every column except the ones that produce a carry, and we handle those carries separately in b.

The line b = carry loads the carry back in for the next round. So the loop folds the carry into the sum again and again. Each pass the carry gets smaller, until it disappears and a holds the final sum.

⏱️ Time and Space Complexity

The loop runs once for each carry that still needs to move. In the worst case the carry ripples across all the bits, so the time is O(k) where k is the bit width, usually 32. It uses only a few variables, so memory is O(1). Since the bit width is fixed, people often call this constant time. The XOR and carry loop is the heart of the answer.

🧩 Key Takeaways

• ✅ Addition splits into a no-carry sum and a carry that moves left.
• ✅ XOR gives the column sum without any carry.
• ✅ AND then a left shift finds where each carry goes.
• ✅ Loop until the carry is zero, then the XOR result is the final sum.
• ✅ This is exactly how hardware adds, using O(1) extra memory.

🚀 What’s Next?

• Single Number
• Number of 1 Bits