{ }DevToolsDaily
ToolsInterview Prep
New
CheatsheetsDirectoryMy spaceBlog
Ctrl + K
Ask AI

Sum of Two Integers – Solution & Complexity

Interview solutions
/
Sum of Two Integers

Solution Walkthrough

  1. Step 1: Understanding the Problem

    • Compute a + b without using the + or - operators — you're only allowed bitwise operations.
    • This is fundamentally about how binary addition works at the hardware level: each bit position produces a sum bit and a carry bit, and the carry ripples into the next position.
    • a XOR b gives the sum of each bit ignoring carries; a AND b (shifted left by 1) gives exactly the carries that need to be added in.

  2. Step 2: XOR for Sum-Without-Carry, AND for Carry

    • a ^ b computes each bit's sum as if there were no carry (since 1^1=0, 0^0=0, 1^0=1 — matches binary addition without carry-out).
    • (a & b) << 1 computes the carry that must be added into the next higher bit position (a carry is produced exactly where both bits are 1, and it affects the next bit up).
    • Repeat: keep adding the running sum and the new carry the same way, until there's no carry left. This is the classic "add via repeated XOR/AND" bit trick, equivalent to how a full-adder circuit ripples carries.

  3. Step 3: Iterating to Convergence

    • Loop: carry = (a & b) << 1, a = a ^ b, b = carry, until b == 0. At that point a holds the final sum.
    • In languages without arbitrary-precision integers (Java/Go/Rust), this must be done with fixed-width (32-bit) arithmetic so negative numbers and overflow wrap around exactly like two's-complement hardware addition — Python needs an explicit mask + sign-fix step since its integers are unbounded.

  4. Step 4: Final Solution (all languages)

    O(1) time in practice — bounded by the fixed bit width (32 iterations max) — and O(1) space.

    def get_sum(a: int, b: int) -> int:
    mask = 0xFFFFFFFF
    while b != 0:
        carry = ((a & b) << 1) & mask
        a = (a ^ b) & mask
        b = carry
    if a > 0x7FFFFFFF:
        a = ~(a ^ mask)
    return a

  5. Step 5: Common mistakes & interviewer follow-ups

    • In Python, forgetting the 32-bit mask/sign-fix step: since Python ints are unbounded, the naive while b: a, b = a ^ b, (a & b) << 1 loop never terminates correctly for negative inputs without explicit masking.
    • In JS, forgetting that << and ^ already operate on 32-bit signed integers, so no extra masking is needed there (unlike Python) — but using them on values outside the 32-bit range gives wrong results.
    • Follow-ups: how would you implement subtraction the same way (hint: a - b == a + (~b + 1), i.e. add the two's-complement negation)? How would this generalize to 64-bit integers?

FAQ

See also

Practice Sum of Two Integers online (run code in the browser)Missing Number solution (easy)Add Two Numbers solution (medium)Climbing Stairs solution (easy)Count Primes solution (medium)All coding interview problems
Buy me a coffeePrivacyTermsFAQChangelogFeature RequestsBlogAll ToolsPricingContact Us © Monkey SkatesHave kids?