The O(n) Club: Sum of Two Integers — Because Who Needs a Plus Sign?

The O(n) Club: Sum of Two Integers — Because Who Needs a Plus Sign?

⚡ TL;DR

Your boss took away + and -, but you still have to add two numbers. Welcome to bitwise hackland: use XOR to add without carry, AND << 1 to figure out the carry, repeat until Java finally coughs up the answer. It’s actual addition, but in a digital trench coat.

// Brute force (interviewer facepalm):
int sum = a + b;
 // Bitwise, the only legal move:
while (b != 0) {
    int carry = (a & b) & 0xFFFFFFFF;
    a = (a ^ b) & 0xFFFFFFFF;
    b = (carry << 1) & 0xFFFFFFFF;
}

🧠 How Devs Usually Mess This Up

Look, everyone wants this to be over in one line. Sadly, XOR only works if you live in a zero-carry universe—which none of us do. If you skip the carry loop, your sum is half-baked. And don’t ignore negatives: Java doesn’t magically sprinkle fairy dust on your bits like Python. Signed 32-bit is the law of the land, so mask your variables or face the Wrath of Two’s Complement.

🔍 What’s Actually Going On

Imagine a binary bakery: XOR is the baker handing out pastries to everyone except those with both hands out (that’s where AND steps in). The carry is just those over-enthusiastic hands passed to the next cycle. Wash, rinse, loop, and eventually you’ll serve pastries with no hands left in the air—and that’s your answer.

🛠️ PseudoCode

• Start with two integers a and b.
• While b != 0:
  • Calculate carry = a & b (the “hands out”).
  • Update a = a ^ b (everyone else gets the pastry).
  • Left shift carry: b = carry << 1 (hands can now try again one position up).
  • For Java, mask with 0xFFFFFFFF so you don’t fall off the 32-bit edge.
• When b == 0, the sum’s done per 32-bit integer logic.
• If a now looks super negative (above Integer.MAX_VALUE), convert back to a negative value with two’s complement magic.

💻 The Code

public int getSum(int a, int b) {
    final int MASK = 0xFFFFFFFF;
    while (b != 0) {
        int carry = (a & b) & MASK;
        a = (a ^ b) & MASK;
        b = (carry << 1) & MASK;
    }
    // Convert back from two's complement if needed
    return (a > Integer.MAX_VALUE) ? ~(a ^ MASK) : a;
}

⚠️ Pitfalls, Traps & Runtime Smacks

• Negative number blues: Don’t forget 32-bit signed logic. Test some edge cases around Integer.MAX_VALUE and Integer.MIN_VALUE or you might get Java’s least fun kind of surprise.
• No plus allowed: Not even inside a clever helper method—interviewers have psychic powers for spotting forbidden syntax.
• Don’t scale mindlessly: This is for int. For long, adjust your mask or enter bug purgatory.
• Time/Space Honesty: Loop runs at most 32 times (one for each bit), so O(1) space, O(1) time in practice, and your CPU will forgive you.

🧠 Interviewer Brain-Tattoo

“If addition was just XOR, calculators would cost $3 and we’d all have more job security.”