Sum of Two Integers

Problem Statement

You are given two integers a and b. Return their sum, but you are not allowed to use the + or - operators to combine them. You have to build the addition yourself out of bitwise operations.

Both inputs can be negative, so the solution has to work with 32-bit two’s complement numbers, not just non-negative values.

Examples

Example 1:

Input: a = 5, b = 9
Output: 14
Explanation: 0101 + 1001 = 1110, which is 14.

Example 2:

Input: a = -7, b = 3
Output: -4
Explanation: In two's complement the carries ripple through the high bits and the result is the 32-bit pattern for -4.

Example 3:

Input: a = -12, b = -30
Output: -42
Explanation: Two negative numbers add to a more negative number; the final carry out of bit 31 is dropped.

Constraints

• -1000 <= a, b <= 1000
• The sum always fits in a signed 32-bit integer.

Approach 1: Bit-by-Bit Ripple-Carry Adder

Algorithm

This is exactly what a hardware ripple-carry adder does. Walk through the 32 bit positions from least significant to most significant, keeping a single carry bit. At each position, the sum bit is the XOR of the two input bits and the incoming carry, and the outgoing carry is 1 when at least two of those three bits are 1.

1. Set result = 0 and carry = 0.
2. For each bit position i from 0 to 31:
   • Read x = bit i of a and y = bit i of b.
   • Sum bit: s = x ^ y ^ carry.
   • New carry: carry = (x & y) | (carry & (x ^ y)).
   • Write s into bit i of result.
3. Any carry out of bit 31 is discarded, which is how 32-bit two’s complement overflow works.
4. Interpret result as a signed 32-bit integer and return it.

Only the loop counter uses ordinary arithmetic; a and b are combined purely with bitwise operators.

Python integers have unlimited width and negative numbers behave as if they had infinitely many leading 1s, so the Python version masks the inputs to 32 bits and converts the final unsigned pattern back to a signed value.

Implementation

Python:

class Solution:
    def getSum(self, a: int, b: int) -> int:
        MASK = 0xFFFFFFFF      # keep 32 bits
        MAX_INT = 0x7FFFFFFF   # largest signed 32-bit value
        a &= MASK
        b &= MASK

        result = 0
        carry = 0
        for i in range(32):
            x = (a >> i) & 1
            y = (b >> i) & 1
            s = x ^ y ^ carry                      # sum bit
            carry = (x & y) | (carry & (x ^ y))    # carry into the next bit
            result |= s << i

        # Bit 31 set means the 32-bit value is negative
        return result if result <= MAX_INT else ~(result ^ MASK)

Java:

class Solution {
    public int getSum(int a, int b) {
        int result = 0;
        int carry = 0;
        for (int i = 0; i < 32; i++) {
            int x = (a >>> i) & 1;
            int y = (b >>> i) & 1;
            int s = x ^ y ^ carry;                    // sum bit
            carry = (x & y) | (carry & (x ^ y));      // carry into the next bit
            result |= s << i;
        }
        // The carry out of bit 31 is dropped; result is already a signed int
        return result;
    }
}

Go:

func getSum(a int, b int) int {
    // Work on the 32-bit two's complement patterns
    ua, ub := uint32(int32(a)), uint32(int32(b))
    var result, carry uint32
    for i := 0; i < 32; i++ {
        x := (ua >> i) & 1
        y := (ub >> i) & 1
        s := x ^ y ^ carry                   // sum bit
        carry = (x & y) | (carry & (x ^ y))  // carry into the next bit
        result |= s << i
    }
    // Reinterpret the bit pattern as a signed 32-bit value
    return int(int32(result))
}

JavaScript:

/**
 * @param {number} a
 * @param {number} b
 * @return {number}
 */
var getSum = function(a, b) {
    let result = 0;
    let carry = 0;
    for (let i = 0; i < 32; i++) {
        const x = (a >>> i) & 1;
        const y = (b >>> i) & 1;
        const s = x ^ y ^ carry;                  // sum bit
        carry = (x & y) | (carry & (x ^ y));      // carry into the next bit
        result |= s << i;                         // bitwise ops keep this a signed 32-bit int
    }
    return result;
};

C#:

public class Solution {
    public int GetSum(int a, int b) {
        uint ua = (uint)a, ub = (uint)b;
        uint result = 0, carry = 0;
        for (int i = 0; i < 32; i++) {
            uint x = (ua >> i) & 1;
            uint y = (ub >> i) & 1;
            uint s = x ^ y ^ carry;                   // sum bit
            carry = (x & y) | (carry & (x ^ y));      // carry into the next bit
            result |= s << i;
        }
        // Reinterpret the bit pattern as a signed 32-bit value
        return unchecked((int)result);
    }
}

C++:

#include <cstdint>

class Solution {
public:
    int getSum(int a, int b) {
        // Unsigned types make every shift and wraparound well defined
        uint32_t ua = static_cast<uint32_t>(a);
        uint32_t ub = static_cast<uint32_t>(b);
        uint32_t result = 0, carry = 0;
        for (int i = 0; i < 32; i++) {
            uint32_t x = (ua >> i) & 1u;
            uint32_t y = (ub >> i) & 1u;
            uint32_t s = x ^ y ^ carry;               // sum bit
            carry = (x & y) | (carry & (x ^ y));      // carry into the next bit
            result |= s << i;
        }
        return static_cast<int32_t>(result);
    }
};

Complexity Analysis

• Time: O(1). The loop always runs exactly 32 times, once per bit of a 32-bit integer.
• Space: O(1). Only a few scalar variables are used.

Approach 2: XOR and Carry Loop (Optimal)

Algorithm

Instead of processing one bit at a time, process all 32 bits in parallel:

• a ^ b adds every bit position at once but ignores carries (1 + 1 becomes 0).
• (a & b) << 1 finds every position that produces a carry and moves that carry to the next position.

The true sum equals (a ^ b) + ((a & b) << 1). That is still an addition, so apply the same trick to those two numbers, and keep going until the carry part becomes zero.

1. While b != 0:
   • carry = (a & b) << 1 (masked to 32 bits where the language needs it).
   • a = a ^ b (partial sum without carries).
   • b = carry.
2. Return a, interpreted as a signed 32-bit integer.

Each round pushes the lowest carry at least one position to the left, so after at most 32 rounds the carry has fallen off the top of a 32-bit word and the loop ends.

The language differences matter here:

• Python: without the & MASK, a negative input makes the carry grow forever because Python integers never overflow. Mask every intermediate value to 32 bits, then convert back to signed at the end with ~(a ^ MASK).
• Java, C#, JavaScript: int (and JavaScript’s bitwise operators) are already 32-bit two’s complement, so the shift silently drops the carry out of bit 31.
• Go: int is 64 bits, so convert to int32 to keep exact 32-bit behavior.
• C++: left-shifting a negative int is undefined before C++20, so do the work in uint32_t.

Implementation

Python:

class Solution:
    def getSum(self, a: int, b: int) -> int:
        MASK = 0xFFFFFFFF      # keep 32 bits
        MAX_INT = 0x7FFFFFFF   # largest signed 32-bit value
        a &= MASK
        b &= MASK

        while b != 0:
            carry = ((a & b) << 1) & MASK   # carries, moved one position left
            a = a ^ b                       # sum without carries
            b = carry

        # Bit 31 set means the 32-bit value is negative
        return a if a <= MAX_INT else ~(a ^ MASK)

Java:

class Solution {
    public int getSum(int a, int b) {
        while (b != 0) {
            int carry = (a & b) << 1;   // carries, moved one position left
            a = a ^ b;                  // sum without carries
            b = carry;                  // add the carries in the next round
        }
        return a;
    }
}

Go:

func getSum(a int, b int) int {
    // Go's int is 64-bit; use int32 to get 32-bit two's complement behavior
    x, y := int32(a), int32(b)
    for y != 0 {
        carry := (x & y) << 1 // carries, moved one position left
        x ^= y                // sum without carries
        y = carry
    }
    return int(x)
}

JavaScript:

/**
 * @param {number} a
 * @param {number} b
 * @return {number}
 */
var getSum = function(a, b) {
    // Bitwise operators work on 32-bit signed integers
    while (b !== 0) {
        const carry = (a & b) << 1; // carries, moved one position left
        a = a ^ b;                  // sum without carries
        b = carry;
    }
    return a;
};

C#:

public class Solution {
    public int GetSum(int a, int b) {
        while (b != 0) {
            int carry = (a & b) << 1;   // carries, moved one position left
            a ^= b;                     // sum without carries
            b = carry;
        }
        return a;
    }
}

C++:

#include <cstdint>

class Solution {
public:
    int getSum(int a, int b) {
        // Shift in unsigned arithmetic: left-shifting a negative int is undefined before C++20
        uint32_t x = static_cast<uint32_t>(a);
        uint32_t y = static_cast<uint32_t>(b);
        while (y != 0) {
            uint32_t carry = (x & y) << 1;  // carries, moved one position left
            x ^= y;                         // sum without carries
            y = carry;
        }
        return static_cast<int32_t>(x);
    }
};

Complexity Analysis

• Time: O(1). Each round moves the lowest carry at least one bit to the left, so the loop runs at most 32 times for 32-bit integers (often far fewer).
• Space: O(1).

Key Insights

• XOR is addition without carry. Per bit, 0+0=0, 0+1=1, 1+0=1, 1+1=0 (carry 1). That truth table is XOR.
• AND finds the carries. A carry is produced only where both bits are 1, and it belongs one position to the left, hence (a & b) << 1.
• Two’s complement makes subtraction free. Negative numbers need no special case: the same bit patterns and the same adder give the right answer as long as you work in a fixed 32-bit width.
• Fixed width is the real requirement. The algorithm terminates because carries fall off the top of a 32-bit word. In a language with unbounded integers (Python) you must create that boundary with a mask.

Edge Cases

• One operand is zero: getSum(0, b) returns b; in Approach 2 the loop does not even run when b == 0.
• Opposite signs that cancel: getSum(5, -5) must return 0. Here the carry ripples all the way through bit 31 and is dropped.
• Both negative: getSum(-1000, -1000) returns -2000; the high bits are all 1s and stay that way.
• Result crosses zero: getSum(-7, 3) returns -4, getSum(7, -3) returns 4.
• Larger values than the constraints: the code is correct for any pair whose sum fits in 32 bits, for example getSum(2147483646, 1).

Common Mistakes

• No mask in Python. getSum(-1, 1) loops forever because the carry keeps shifting into ever higher bits of an unbounded integer.
• Forgetting to convert back to signed in Python. After masking, -4 is stored as 4294967292; return ~(a ^ MASK) when bit 31 is set.
• Using Go’s 64-bit int while assuming 32-bit behavior. It gives the right answer within the constraints, but it no longer models a 32-bit adder: the loop can take up to 64 rounds and sums that overflow 32 bits are not wrapped. Convert to int32.
• Shifting negative signed values in C++. Use uint32_t (or unsigned) for the shifts.
• Updating a before computing the carry. The carry must be computed from the old a and b, so save it before overwriting a.

Interview Tips

• Start by writing the per-bit truth table of addition; the XOR/AND observation falls straight out of it and shows the interviewer you derived it rather than memorized it.
• Walk through a small example such as 5 + 9 on paper, showing the partial sum and carry for each round.
• Bring up negative numbers before you are asked, and explain how your language represents them. In Python, explain the mask and the signed conversion.
• Be ready to argue why the loop terminates: the lowest set bit of the carry moves left every round.

Follow-up Questions

• How would you subtract without -? Compute a + (~b + 1), using the same bitwise adder for both additions, since ~b + 1 is the two’s complement negation of b.
• How would you multiply without *? Shift-and-add: for each set bit i of b, add a << i to the result using the bitwise adder.
• What changes for 64-bit integers? Only the width: use a 64-bit mask in Python and 64-bit types elsewhere; the loop runs at most 64 times.
• Is Approach 2 always faster than Approach 1? Usually, since it stops as soon as the carry is zero, but its worst case is still 32 rounds.

Related Problems

• Number of 1 Bits
• Counting Bits
• Single Number
• Reverse Bits
• Power of Two