Sum of Two Integers

MEDIUM✓ CHIP-TIMEDLC #371 — FULL STATEMENT ↗

The drill: Add two integers without touching the + or − operators — only bitwise moves are allowed, which means building addition back up from AND, XOR and shifts.

THE BRIEFING — THE FULL DRILL, IN MY OWN WORDS

Two signed integers arrive, and the task is to produce their sum — but the classic + operator, and its cousin −, are both off-limits as the solving technique.

The result must equal what ordinary addition would produce, negative numbers included, reached instead through bitwise operations and shifts alone.

Both inputs can be negative, zero, or positive, and the sum itself must behave like standard signed addition, wrapping the same way that arithmetic normally would.

EX 01

a = 1 · b = 2

→ 3

SIMPLE POSITIVE SUM

EX 02

a = -1 · b = 1

→ 0

NEGATIVE AND POSITIVE CANCEL

EX 03

a = 0 · b = 0

→ 0

BOTH ZERO

both a and b are signed integers within ordinary 32-bit range
either value can be negative, zero, or positive
the + and − operators may not appear in the solving technique itself
the result must match standard signed 32-bit addition, wraparound included

THE HINTS — TAKE ONLY WHAT YOU NEED

HINT 1 THE NUDGE

Repeating a plain unit step a bunch of times gets you there and never writes a real addition between the two original numbers — but watch how slow that gets as the gap grows.

HINT 2 THE STRUCTURE

XOR adds two bits ignoring any carry; AND tells you exactly where a carry would be generated. The real problem is that a carry can itself trigger more carries.

HINT 3 ONE STEP FROM THE ANSWER

Loop: new sum = a XOR b, new carry = (a AND b) shifted left one place. Keep feeding sum and carry back in as the new a and b until the carry hits zero.

COACH'S BOARD — THE PATTERN, STEP BY STEP

THE CARRY LOOPPATTERN · CARRY PROPAGATIONa = 15 · b = 27

A / B (BINARY)

a → 15 (001111)

b → 27 (011011)

STEP 1

Add 15 and 27 without + or −: XOR gives the sum ignoring carries, AND shifted left gives exactly where the next carry lands.

STEP 1 / 6 · ← → WORK TOO

THE SPLITS — TWO PACES, TWO LANGUAGES

grind/sum-of-two-integers.py — RACE PACE

LANG ▸

PACE ▸

class Solution:
    def getSum(self, a: int, b: int) -> int:
        mask = 0xFFFFFFFF
        a &= mask
        b &= mask
        while b:
            carry = (a & b) << 1 & mask
            a = (a ^ b) & mask
            b = carry
        # a now holds the 32-bit two's complement pattern; re-sign it.
        if a > 0x7FFFFFFF:
            a -= 0x100000000
        return a

TIME O(32)SPACE O(1)PYTHON · RACE PACE · 13 LN

class Solution:
    def getSum(self, a: int, b: int) -> int:
        cur = a
        step = 1 if b > 0 else -1
        for _ in range(abs(b)):
            cur += step
        # Python ints never overflow, so wrap the final result to 32-bit signed by hand.
        cur &= 0xFFFFFFFF
        if cur > 0x7FFFFFFF:
            cur -= 0x100000000
        return cur

TIME O(|B|)SPACE O(1)PYTHON · TRAINING PACE · 11 LN

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

TIME O(32)SPACE O(1)JAVA · RACE PACE · 10 LN

class Solution {
    public int getSum(int a, int b) {
        int cur = a;
        int step = b > 0 ? 1 : -1;
        int remaining = Math.abs(b);
        // Java's int naturally wraps on overflow, matching 32-bit two's complement.
        for (int i = 0; i < remaining; i++) {
            cur += step;
        }
        return cur;
    }
}

TIME O(|B|)SPACE O(1)JAVA · TRAINING PACE · 12 LN

✓ CHIP-TIMED — ALL 4 SOLUTIONS RAN GREEN AGAINST SELF-AUTHORED CASES IN CI · JDK 21 · CPYTHON 3.12 · NOTHING PUBLISHES RED