LeetCode 371: Sum of Two Integers Explained | Java | Bit Manipulation | Blind 75

Learn how computers add numbers using XOR and Carry operations with visuals, dry runs, and interview tips

Have you ever wondered how a computer adds two numbers internally?

When we write:

5 + 3 = 8

we use the + operator.

But inside a computer, addition is not performed using a magic + button.

At the hardware level, addition is performed using bit operations, mainly:

• XOR (^) for adding bits without carry
• AND (&) with shifting for handling carry

This problem asks us to recreate that behavior using only Bit Manipulation.

Companies like Google, Microsoft, Amazon, Meta, and Apple love this problem because it tests whether you understand how numbers are represented and manipulated at the binary level.

In this article, we’ll build the intuition behind Sum of Two Integers (LeetCode 371) from the Blind 75 list.

What You’ll Learn

By the end of this article you’ll know:

✅ How computers perform binary addition

✅ Why XOR behaves like addition without carry

✅ How AND helps calculate carry

✅ How to add numbers without using + or -

✅ Dry Run

✅ Time Complexity

✅ Interview Tips

✅ Related Problems

Problem Statement

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

Example 1

Input

a = 1
b = 2

Output

3

Example 2

Input

a = 2
b = 3

Output

5

Real World Analogy

Imagine you are designing a calculator chip.

When a user enters:

5 + 3

the chip cannot understand addition like humans do.

Instead, it works with tiny electrical switches called bits.

Each switch can be:

• OFF (0)
• ON (1)

The calculator combines these switches one position at a time.

Sometimes two switches combine normally:

0 + 1 = 1

Sometimes both switches are ON:

1 + 1 = 10

In this case:

• The current position becomes 0.
• A carry is sent to the next position.

Your task is to simulate this process using only basic bit operations, just like the hardware inside a computer.

This is exactly what the problem asks — perform addition without using the normal addition operator.

Important Concepts

Binary Addition

Computers store numbers as binary.

Example:

Decimal 5 = 0101

Decimal 3 = 0011

Normal addition:

0101
+  0011
-------
   1000

Result:

8

XOR Operation

XOR gives the addition result without considering carry.

Truth table:

0 ^ 0 = 0

0 ^ 1 = 1

1 ^ 0 = 1

1 ^ 1 = 0

Notice:

1 + 1 = 10

XOR keeps only the right side:

1 ^ 1 = 0

The carry is handled separately.

Carry Calculation

When both bits are 1, a carry is generated.

We detect this using:

a & b

Example:

1 & 1 = 1

But the carry belongs to the next position, so we shift it left:

(a & b) << 1

Approach 1: Bit-by-Bit Addition (Building Intuition)

Before jumping to the optimal solution, let’s understand how binary addition works.

For every bit position:

1. Add the bits without carry.
2. Find where carry occurs.
3. Move the carry to the next position.

This is exactly how a hardware component called a Full Adder works.

Example

Add:

5 + 3

Binary:

0101
+ 0011
------

Step 1: Add without carry

Using XOR:

0101
0011
----
0110

Current result:

6

Step 2: Find carry

Using AND:

0101
0011
----
0001

Shift left:

0010

Carry:

2

Now we need to add:

6 + 2

We repeat the same process.

Can We Do Better?

Yes.

Instead of manually checking every bit position, we repeat the same two operations:

1. XOR gives the temporary sum.
2. AND + shift gives the carry.

We continue until there is no carry left.

This gives us the optimal solution.

Approach 2: XOR + Carry (Optimal)

The key idea:

Sum without carry

sum = a ^ b

Because XOR handles all normal bit additions.

Carry

carry = (a & b) << 1

Because AND finds positions where both bits are 1.

The left shift moves the carry to the correct position.

Then:

• Replace a with the sum.
• Replace b with the carry.
• Repeat until carry becomes zero.

Algorithm

1. While b is not zero:
2. Calculate carry:

carry = (a & b) << 1

1. Calculate sum:

a = a ^ b

1. Move carry:

b = carry

1. Return a.

Dry Run

Example:

a = 5

b = 3

Binary:

a = 0101

b = 0011

Iteration 1

XOR:

0101
0011
----
0110

a = 6

Carry:

0101
0011
----
0001

Shift:

0010

b = 2

Iteration 2

Now:

a = 0110

b = 0010

XOR:

0110
0010
----
0100

a = 4

Carry:

0110
0010
----
0010

Shift:

0100

b = 4

Iteration 3

a = 0100

b = 0100

XOR:

0000

Carry:

1000

Iteration 4

a = 1000

b = 0000

No carry remains.

Answer:

8

Java Code

class Solution {

    public int getSum(int a, int b) {

        while (b != 0) {

            int carry = (a & b) << 1;

            a = a ^ b;

            b = carry;
        }

        return a;
    }
}

Complexity Analysis

Time Complexity: O(32)

An integer contains 32 bits.

In the worst case, every bit may need to be processed.

Space Complexity: O(1)

Only constant variables are used.

Why Does XOR Work as Addition?

XOR follows the same rule as binary addition without carry:

0 + 0 = 0

0 + 1 = 1

1 + 0 = 1

1 + 1 = 0 (carry generated)

The only missing case is:

1 + 1

The carry handles that.

So:

XOR = Sum without carry

AND + Left Shift = Carry

Together:

Addition = XOR + Carry

Interview Tips ⭐

Whenever you see:

• “Add two numbers without using +”
• “Implement addition manually”
• “Use bit manipulation”

Think about:

XOR → Sum

AND + Shift → Carry

This pattern is the foundation of binary addition.

Common Mistakes

❌ Forgetting the left shift

Wrong:

carry = a & b;

Correct:

carry = (a & b) << 1;

The carry moves to the next bit position.

❌ Using normal addition

The whole point of this problem is avoiding:

a + b

❌ Ignoring negative numbers

Java integers use two’s complement representation, and the same logic works for negative values because int always has 32 bits.

💡 Key Takeaway

This problem teaches how computers actually perform addition.

Remember these two rules:

XOR → Adds bits without carry

AND + Shift → Creates carry

Once you understand this pattern, many advanced bit manipulation problems become much easier.

Conclusion

Sum of Two Integers looks like a mathematical problem, but the real challenge is understanding how numbers work internally.

We explored:

1. Binary addition using XOR and carry.
2. An optimal bit manipulation solution.

This problem is one of the best examples of how low-level computer operations can be recreated using simple bit operations.

This article is part of my Blind 75 in Java series.

➡️ Next: Number of Islands (LeetCode 200)

If you found this article helpful, consider following me for more beginner-friendly Java interview solutions.

Happy coding! 🚀