Sweaty Imposter

Sum of Two Integers

MediumBitwise XORBlind 75MidOpen on LeetCodeUpdated

You're given two integers a and b. Return their sum without using the + or - operators. Either value may be negative, and the result fits in a 32-bit signed integer.

Examples

a = 3, b = 9 returns 12

In binary, 0011 XOR 1001 is 1010 (the sum without carries) and the shared bit 0001 carries into 0010. Adding those two gives 1100, which is 12.

a = -6, b = 4 returns -2

Two's complement makes negative numbers add with the same bit rules as positive ones.

a = -5, b = -7 returns -12

Both inputs are negative, and the carry chain still settles within 32 bits.

Constraints

  • -1000 <= a, b <= 1000

Hints

Hint 1

Think about adding two binary numbers by hand. Which bitwise operator gives each column's digit if you ignore carries?

Hint 2
A pointer toward the approach
Hint 3
The full approach, step by step

Drill This: Your Approach First

Approach

Binary addition splits into two parts: a XOR b is the sum of each bit position ignoring carries, and (a AND b) shifted left by one is the carry each position sends to the next. Replace a with the XOR and b with the carry, and repeat until no carry is left. Each round pushes the carries at least one position left, so the loop ends within 32 rounds. Python integers have no fixed width, so mask every intermediate value to 32 bits and convert the result back to a signed number at the end.

Time

O(1)

Space

O(1)

Pitfall

Porting the Java loop straight to Python. A negative Python integer has infinitely many leading 1 bits, so the carry never shifts out and the loop runs forever. Mask with 0xFFFFFFFF on each step and sign-extend the final value.

Solutions

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