LeetCode 371 · Bit Manipulation

Sum of Two Integers, explained with a picture

Adding without +: sparks carry to the left.

MediumBit Manipulation
▶ Watch it step by step

The problem

Add two integers without using + or −.

Input:  a = 5, b = −7
Output: −2

Picture it

Picture two switch panels added column by column. XOR gives each column’s sum without carries (1 + 1 = 0). AND finds the columns where both are 1, which produce a carry spark that jumps one column to the left. Repeat with (sum without carries, carries shifted left) until there are no more carries.

How to recognise it

  • You must add without + or -, so the only tools are bit operators: ^, &, <<, >>, ~.
  • Binary addition splits into two parts: the sum without carries (that is XOR) and the carries (that is AND, moved one place left).
  • Negative numbers are involved, so you need the 32-bit two's complement view: a fixed width where the top bit means negative.
  • Inputs are between −1000 and 1000 on LeetCode, so speed is never the issue; correctness with negatives is.

Start with brute force

Do what a hardware adder does: walk the 32 bit positions from right to left, computing each output bit and the carry into the next position.

def add_ripple(a, b):
    M = 0xFFFFFFFF
    a, b = a & M, b & M
    out, carry = 0, 0
    for i in range(32):                  # one bit position at a time
        x, y = (a >> i) & 1, (b >> i) & 1
        out |= (x ^ y ^ carry) << i
        carry = (x & y) | (carry & (x ^ y))
    if out > 0x7FFFFFFF:
        out = ~(out ^ M)
    return out

This always takes 32 steps, O(1) for fixed width, so it is not slow. It handles one bit at a time, while the shown code handles all 32 positions in each round.

From brute force to the idea

  1. Find the waste. The ripple loop processes one position per step even though ^ and & work on all 32 positions at once.
  2. Split the sum. a ^ b adds every position while ignoring carries. (a & b) << 1 is where a carry is created (both bits 1), moved to the position it carries into.
  3. Add the carries in. The true sum is (sum without carry) + (carry). That is another addition, so repeat with a = a ^ b and b = carry until no carry is left (b == 0).
  4. Keep it 32 bits. Python integers have unlimited width, so a negative number has infinitely many leading 1 bits, and without a limit the carry can move left forever. & M (32 one bits) after each step keeps everything inside 32 bits. Each round moves the lowest carry bit at least one place left, so there are at most 32 rounds.
  5. Read the sign back. If the result's top bit is set (above 0x7FFFFFFF), it stands for a negative number. a ^ M flips the 32 low bits and ~ flips everything, which sets all the infinite upper bits: the Python negative value.

This is the key idea: sum = XOR (no carry) plus AND shifted left (the carry), repeated until the carry is 0, all masked to 32 bits.

The key idea

sum = a ^ b, carry = (a & b) << 1; repeat until carry is 0. Python integers have no fixed width, so a negative number acts like endless 1-bits and the carry never dies out: mask every step with M = 0xFFFFFFFF to stay in 32 bits, and at the end turn a pattern with the top bit on back into a negative with ~(a ^ M).

Python solution

def get_sum(a, b):
    M = 0xFFFFFFFF            # 32 one-bits
    a, b = a & M, b & M       # 32-bit view
    while b:
        carry = ((a & b) << 1) & M
        a = (a ^ b) & M  # add, no carry
        b = carry
    if a > 0x7FFFFFFF:        # top bit on:
        a = ~(a ^ M)  # it is negative
    return a

In the interactive version each line lights up as the animation runs, and you can type your own input to see the algorithm handle it.

Complexity

ApproachTimeSpace
Ripple-carry loopO(32): one step per bit positionO(1)
XOR and carry rounds (shown code)O(32) worst case: at most 32 rounds, usually far fewerO(1)

Edge cases

  • The example get_sum(5, -7): returns −2.
  • Opposite numbers (-1 and 1): the carry runs through all 32 positions, taking 32 rounds, and the result is 0.
  • Zero: get_sum(0, 0) is 0; the loop does not run.
  • Results outside 32 bits wrap around like a real 32-bit integer: get_sum(2**31 - 1, 1) returns −2147483648. With LeetCode's inputs (±1000) this never happens.

Common mistakes

  • Leaving out the & M masks in Python: get_sum(-1, 1) then never finishes, because the carry keeps moving into ever-higher bits.
  • Forgetting the final sign step, so negative results come back as large positive numbers (5 + (−7) gives 4294967294).
  • Using a + b or sum([a, b]), which breaks the rule of the problem.
  • Shifting the carry before the AND ((a << 1) & b), which builds the wrong carry.
Your turn: subtract without minus

Compute a − b without + or -, for 32-bit integers. You may call get_sum. Describe your approach, then write it if you like.

Compare with our answer

In two's complement, −b equals ~b + 1 (flip every bit, then add 1). So a − b = a + ~b + 1, and both additions can be done with get_sum. The literal 1 is a number, not a minus sign.

def get_diff(a, b):
    return get_sum(get_sum(a, ~b), 1)    # a - b = a + (~b) + 1

get_diff(5, 7) is −2. Time O(32), space O(1). Results outside 32 bits wrap around, just as for get_sum.

A strong answer mentions: two's complement negation as "flip and add one", reusing the adder twice, and the same 32-bit wrap-around.

Check what stuck

1. You must multiply two non-negative integers without *, using only bit operators and an adder. Which approach fits best?

2. Why does the shown code apply & M inside the loop in Python?

3. A learner deletes the last two lines before return a (the sign check). What does get_sum(5, -7) return?

Score 60% or more and the lesson is marked complete.