Sum of Two Integers

Addition on binary digits is exactly what a hardware adder does: XOR gives the sum of two bits ignoring any carry, and AND gives the positions where a carry is generated (which then gets shifted one place left to be added in). Repeating that — “add without carry, then add the carry in” — until there is no carry left reproduces + using only ^, &, and <<.

Bit-by-Bit Carry Propagation

OptimalTime O(32) = O(1)Space O(1)

a ^ b sums each bit position without carrying. (a & b) << 1 computes the carry that addition would have produced at each position, shifted into its correct destination. Repeatedly replace (a, b) with (a ^ b, carry) until the carry becomes 0 — at that point a alone holds the finished sum.

Python integers are arbitrary-precision, so without care this loop would never terminate for negative numbers (the carry keeps propagating into infinitely many virtual sign bits). To match the 32-bit signed-integer semantics the problem intends, every value is masked down to 32 bits (mask = 0xFFFFFFFF) at each step, and the final result is converted back from a 32-bit unsigned pattern to a signed Python int if its top bit is set.

class Solution:
    def getSum(self, a: int, b: int) -> int:
        mask = 0xFFFFFFFF
        while b & mask:
            carry = (a & b) << 1
            a = a ^ b
            b = carry
        a &= mask
        # a's bit 31 set means the 32-bit pattern represents a negative number
        if a > 0x7FFFFFFF:
            return ~(a ^ mask)
        return a

Watch the carry row get shifted left and folded back into the sum until the loop check says b is 0:

Round 1start

3210

a0010

b0011

a ^ b····new a

carry····new b

Loop checkb is not 0 → loopresult—

1 / 8

currentcomparingresult

Start: a = 2 (0010) and b = 3 (0011). Each loop round does two jobs: sum the bits without carries, then fold the carries back in.

Tracing a = 2 (0b010), b = 3 (0b011):

a=010, b=011:  a^b = 001 (sum without carry), (a&b)<<1 = 010<<1 = 100 (carry)
a=001, b=100:  a^b = 101 (sum without carry), (a&b)<<1 = 000<<1 = 000 (no carry left)
a=101, b=000:  loop ends (b & mask == 0) -> result = 0b101 = 5

For a negative example, a = -1, b = 1: masked to 32 bits, -1 is 0xFFFFFFFF and 1 is 0x00000001. XOR gives 0xFFFFFFFE, carry (a & b) << 1 = 1 << 1 = 0x2. Next round XORs 0xFFFFFFFE ^ 0x2 = 0xFFFFFFFC… this keeps shifting the single carry bit left until it falls off the top of the 32-bit mask and b & mask becomes 0, leaving a = 0, correctly -1 + 1 = 0.

Complexity: each round either clears a bit of b or shifts the carry one position higher, so it terminates in at most 32 rounds → O(1) time (bounded by the fixed 32-bit width), O(1) space.

Sum of Two Integers

Bit-by-Bit Carry Propagation

More Bit Manipulation practice