Skip to main content
CodePeetCodePeet
CodePeet 250

Sum of Two Integers

MEDIUMProblemSolveExternal Links

Description

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

In other words, you need to find a way to add two numbers together using only bitwise operations such as AND, OR, XOR, and bit shifts. This problem tests your understanding of how addition works at the binary level — the same way a computer's hardware actually adds numbers.

Examples

Example 1

Input: a = 1, b = 2

Output: 3

Explanation: In binary, 1 is 01 and 2 is 10. When we add them bit by bit: in the ones place 1 + 0 = 1, and in the twos place 0 + 1 = 1, giving us 11 which is 3 in decimal. There is no carry at any bit position, so XOR alone produces the result.

Example 2

Input: a = 2, b = 3

Output: 5

Explanation: In binary, 2 is 10 and 3 is 11. In the ones place 0 + 1 = 1 (no carry). In the twos place 1 + 1 = 0 with a carry of 1 to the fours place. The fours place gets just the carry, so the result is 101 which is 5.

Example 3

Input: a = -1, b = 2

Output: 1

Explanation: Negative numbers are stored in two's complement form. -1 in 32-bit binary is all 1s: 11111111111111111111111111111111. Adding 2 (10) to this using bitwise operations propagates carries until the result wraps around to 00000000000000000000000000000001 which is 1.

Constraints

  • -1000 ≤ a, b ≤ 1000

Editorial

Brute Force

Intuition

The most natural way to think about adding without + or - is to go back to how we learned addition in school — processing one digit (bit) at a time from right to left, keeping track of a carry.

Imagine you have two binary numbers written on paper. You look at the rightmost column first: add the two bits and the carry from the previous column. If the sum is 0 or 1, write it down with no carry. If the sum is 2, write 0 and carry 1. If the sum is 3, write 1 and carry 1. This is exactly how a "full adder" circuit works inside a CPU.

We can simulate this process by extracting one bit at a time from each number using bit masking, computing the result bit and carry, and building the answer bit by bit.

Step-by-Step Explanation

Let's trace through with a = 2 (binary 10), b = 3 (binary 11):

Step 1: Initialize result = 0, carry = 0. We will process 32 bits (for a 32-bit integer), but we only need a few here.

Step 2: Bit position 0 (rightmost): Extract bit 0 of a → 0. Extract bit 0 of b → 1. Sum with carry: 0 + 1 + 0 = 1. Result bit = 1, new carry = 0. Set bit 0 of result → result = 1 (decimal 1).

Step 3: Bit position 1: Extract bit 1 of a → 1. Extract bit 1 of b → 1. Sum with carry: 1 + 1 + 0 = 2. Result bit = 0, new carry = 1. Set bit 1 of result → result = 01 (decimal 1).

Step 4: Bit position 2: Extract bit 2 of a → 0. Extract bit 2 of b → 0. Sum with carry: 0 + 0 + 1 = 1. Result bit = 1, new carry = 0. Set bit 2 of result → result = 101 (decimal 5).

Step 5: Remaining bit positions all have 0 + 0 + 0 = 0, so no more changes.

Step 6: Return result = 5.

Bit-by-Bit Full Adder Simulation — Watch how we extract each bit from a and b, compute the sum bit and carry, and build the result one bit at a time — just like hardware addition.

Algorithm

  1. Initialize result = 0 and carry = 0
  2. For each bit position i from 0 to 31:
    • Extract bit i from a: bit_a = (a >> i) & 1
    • Extract bit i from b: bit_b = (b >> i) & 1
    • Compute total = bit_a + bit_b + carry (using built-in add for single bits — this is a constant addition of values 0 or 1, which some interpretations allow; alternatively compute with XOR/AND)
    • result_bit = total % 2 (or total & 1)
    • carry = total / 2 (or total >> 1)
    • Set bit i of result: result |= (result_bit << i)
  3. Return result

Code

class Solution {
public:
    int getSum(int a, int b) {
        int result = 0;
        int carry = 0;
        for (int i = 0; i < 32; i++) {
            int bit_a = (a >> i) & 1;
            int bit_b = (b >> i) & 1;
            // XOR of three single bits gives the sum bit
            int sum_bit = bit_a ^ bit_b ^ carry;
            // Carry is generated when at least two of the three bits are 1
            carry = (bit_a & bit_b) | (bit_a & carry) | (bit_b & carry);
            result |= (sum_bit << i);
        }
        return result;
    }
};
class Solution:
    def getSum(self, a: int, b: int) -> int:
        MASK = 0xFFFFFFFF
        MAX_INT = 0x7FFFFFFF
        
        # Work in 32-bit space
        a_masked = a & MASK
        b_masked = b & MASK
        
        result = 0
        carry = 0
        for i in range(32):
            bit_a = (a_masked >> i) & 1
            bit_b = (b_masked >> i) & 1
            sum_bit = bit_a ^ bit_b ^ carry
            carry = (bit_a & bit_b) | (bit_a & carry) | (bit_b & carry)
            result |= (sum_bit << i)
        
        # Handle negative results in Python (which has arbitrary precision)
        if result > MAX_INT:
            result = ~(result ^ MASK)
        return result
class Solution {
    public int getSum(int a, int b) {
        int result = 0;
        int carry = 0;
        for (int i = 0; i < 32; i++) {
            int bitA = (a >> i) & 1;
            int bitB = (b >> i) & 1;
            int sumBit = bitA ^ bitB ^ carry;
            carry = (bitA & bitB) | (bitA & carry) | (bitB & carry);
            result |= (sumBit << i);
        }
        return result;
    }
}

Complexity Analysis

Time Complexity: O(32) = O(1)

We always iterate exactly 32 times (once per bit in a 32-bit integer). Each iteration does a constant number of bitwise operations. Since the number of iterations is fixed and does not depend on the magnitude of a or b, this is O(1).

Space Complexity: O(1)

We use only a handful of integer variables (result, carry, bit_a, bit_b, sum_bit), none of which grow with input size.

Why This Approach Is Not Efficient

While the bit-by-bit full adder approach works correctly and runs in O(1) time, it is unnecessarily verbose. We are manually looping through all 32 bit positions and extracting individual bits, even though most positions may not contribute anything meaningful (especially for small numbers like those in our constraints: -1000 ≤ a, b ≤ 1000, which only use about 10-11 bits).

More importantly, this approach misses a fundamental insight: we do not need to process bits individually. Bitwise operators like XOR and AND already operate on ALL bits simultaneously in a single instruction. If we can express the entire addition in terms of whole-number XOR and AND operations, we can eliminate the per-bit loop entirely and let the hardware process all 32 bits in parallel.

The key observation is:

  • a XOR b gives us the sum of a and b at every bit position where there is no carry (it adds bits without carrying)
  • (a AND b) << 1 gives us the carry at every position (it finds where both bits are 1 and shifts that carry to the next position)
  • We then just need to "add" these two results — which is the same problem again, but the carry shrinks each iteration until it reaches zero.

Optimal Approach - Iterative Bit Manipulation (XOR + AND)

Intuition

Think about how you add two single-digit binary numbers:

  • 0 + 0 = 0 (no sum, no carry)
  • 0 + 1 = 1 (sum is 1, no carry)
  • 1 + 0 = 1 (sum is 1, no carry)
  • 1 + 1 = 10 (sum digit is 0, carry is 1)

Notice something? The "sum without carry" column is exactly the XOR truth table, and the "carry" column is exactly the AND truth table! This is not a coincidence — it is how binary addition fundamentally works.

So for multi-bit numbers:

  • a ^ b computes the sum at every bit position, ignoring carries
  • (a & b) << 1 computes all the carries and shifts them to the next position

Now we need to add the partial sum and the carry together. But wait — that is the same problem (adding two numbers)! The trick is that the carry has fewer set bits each time, so eventually the carry becomes zero and we are done.

Imagine adding in decimal: 27 + 35. Without carries: 52 (7+5=2 write 2, 2+3=5 write 5). Carries: 10 (7+5 generates a carry of 1 into the tens place). Now add 52 + 10 = 62. The carry disappears after one round. The same principle works in binary.

Diagram showing how XOR computes sum-without-carry and AND computes carry for binary addition
Diagram showing how XOR computes sum-without-carry and AND computes carry for binary addition

Step-by-Step Explanation

Let's trace through with a = 2 (binary 0010), b = 3 (binary 0011):

Step 1: Initialize: a = 2 (0010), b = 3 (0011). We need to find a + b using only XOR and AND.

Step 2: Compute sum without carry: a ^ b = 0010 ^ 0011 = 0001 (decimal 1). This adds each bit position independently — position 0: 0⊕1=1, position 1: 1⊕1=0.

Step 3: Compute carry: (a & b) << 1 = (0010 & 0011) << 1 = 0010 << 1 = 0100 (decimal 4). Both bits at position 1 were 1, generating a carry that shifts to position 2.

Step 4: Update: a = 0001 (the partial sum), b = 0100 (the carry). Now we need to add these two.

Step 5: Compute sum without carry: a ^ b = 0001 ^ 0100 = 0101 (decimal 5). No bit positions overlap, so XOR gives the complete sum.

Step 6: Compute carry: (a & b) << 1 = (0001 & 0100) << 1 = 0000 << 1 = 0000 (decimal 0). No positions have both bits set, so no carry is generated.

Step 7: b (carry) is now 0, so we stop. The answer is a = 5.

Result: 2 + 3 = 5.

XOR + Carry Iteration — Adding 2 and 3 — Watch how XOR computes the sum-without-carry and AND-shift computes the carry. Each iteration, the carry shrinks until it becomes zero.

Algorithm

  1. While b (the carry) is not zero:
    a. Compute the carry: carry = (a & b) << 1
    b. Compute the sum without carry: a = a ^ b
    c. Update b = carry
  2. Return a

Note for Python: Since Python integers have arbitrary precision (no fixed 32-bit boundary), negative numbers require masking to 32 bits using & 0xFFFFFFFF to simulate overflow behavior.

Code

class Solution {
public:
    int getSum(int a, int b) {
        while (b != 0) {
            // carry contains common set bits shifted left
            int carry = (a & b) << 1;
            // XOR gives sum without carry
            a = a ^ b;
            // carry becomes the new b
            b = carry;
        }
        return a;
    }
};
class Solution:
    def getSum(self, a: int, b: int) -> int:
        MASK = 0xFFFFFFFF  # 32-bit mask
        MAX_INT = 0x7FFFFFFF  # max positive 32-bit int
        
        # Mask both to work in 32-bit unsigned space
        a, b = a & MASK, b & MASK
        
        while b != 0:
            carry = ((a & b) << 1) & MASK
            a = (a ^ b) & MASK
            b = carry
        
        # If result > MAX_INT, it's negative in 32-bit two's complement
        return a if a <= MAX_INT else ~(a ^ MASK)
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(1)

The loop runs at most 32 times for 32-bit integers. In each iteration, the carry bit pattern shifts left by at least one position. Since there are only 32 bit positions, the carry must eventually become zero within 32 iterations. Each iteration performs a constant number of bitwise operations (AND, XOR, shift). Therefore the total work is bounded by a constant.

Space Complexity: O(1)

We use only two variables (a and b, plus a temporary carry). No additional data structures are needed. The space usage does not depend on the input values.