Understand
30-second explanation
Build the interview-ready mental model before comparing implementations.
Add two integers without using + or -. The insight: XOR is addition with the carries ignored (`a ^ b`), and `(a & b) << 1` is exactly those carries shifted into the next column. Loop — add the sum-without-carry, recompute the carry, repeat — until the carry is 0. In Python you must mask with `& 0xFFFFFFFF` to emulate fixed-width 32-bit overflow.
Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview contextHide interview context
What's being tested
Whether you understand addition at the bit level — that XOR is the carry-less sum and AND-then-shift is the carry — and whether you can emulate fixed-width two's-complement arithmetic in a language (Python) that has none.
Where candidates slip
Not masking in Python, so a negative input makes the carry loop run forever (the carry never clears in an infinite-precision int), or returning a huge positive number instead of converting the 32-bit pattern back to a signed negative.
How to stand out
Explain the full-adder analogy (XOR = sum bit, carry = AND), state why the loop terminates (carries march left and fall off), and proactively handle Python's masking and negative-result conversion without being prompted.
Choose
Compare the available approaches
Use constraints and trade-offs to select the route you can defend in an interview.
Interactive decision treeInteractiveChoose the right approachFirst decision previewAdd a + b without + or −Iterate fixed 32 positions, or loop on the carry?Per positionLoop on carryExplore the full treeCollapse the tree
Learn & trace
Build each solution step by step
Move from the core idea to a visual trace, implementation, proof, and edge cases.
Approach 1 of 2
Full-Adder — Sum and Carry Per Bit
1Hint 1Explore hintHide hint
Think about how a single column of binary addition works: two input bits plus an incoming carry produce a sum bit and an outgoing carry.
2Hint 2Explore hintHide hint
The sum bit is bitA ^ bitB ^ carry. The outgoing carry is set when at least two of the three inputs are 1.
3Hint 3Explore hintHide hint
Walk all 32 positions low to high, building the result bit by bit and threading the carry from one column to the next.
A · Core idea
Simulate grade-school binary addition one column at a time. At bit position i, take bitA, bitB, and the incoming carry; the result bit is their three-way XOR, and the outgoing carry is 1 when two or more of them are set. Thread the carry into the next position and assemble the result.
Why the sum bit is `bitA ^ bitB ^ carry`. A binary column outputs 1 when an odd number of its three inputs are 1 — that's the definition of XOR over three bits. Two 1s sum to 10 (digit 0, carry out), three 1s sum to 11 (digit 1, carry out). XOR captures exactly the digit.
Why the carry is the majority. A column carries into the next when at least two inputs are 1: (bitA & bitB) | (carry & (bitA ^ bitB)). The first term catches 'both inputs set'; the second catches 'exactly one input set plus an incoming carry'. Together that's the majority function — the classic full-adder carry.
Why this handles negatives for free in Java. Reading (a >> i) & 1 across all 32 positions, including the sign bit at position 31, reconstructs the two's-complement value, and writing the sign bit back makes the result negative when appropriate. Java's int is already 32-bit two's complement, so no masking is needed. In Python, the bits are the same but the assembled result is a plain non-negative int, so if bit 31 is set we convert it back to a signed value with ~(result ^ 0xFFFFFFFF).
B · Visual dry run
Interactive dry run
Select a frame to connect the decision with its visual state.
a = 2 (10), b = 3 (11)Interactive diagram
Carry threading through the columns
i=0Each column emits a sum bit and feeds a carry into the next column to the left.
5C · Code with teaching comments
Reference implementation previewpublic int getSum(int a, int b) { int result = 0, carry = 0; for (int i = 0; i < 32; i++) { int bitA = (a >> i) & 1; int bitB = (b >> i) & 1;Explore the full codeHide the full code
D · Why it works and complexityO(32) = O(1) timeO(1) spaceOpen the invariant and proofExplore the proofHide the proof
This is literally a row of 32 full adders drawn in software — the same circuit inside every CPU's ALU. Seeing addition decompose into 'XOR for the digit, majority for the carry' demystifies why the compact XOR/carry loop (the next approach) works: it's this same logic, vectorised across all bits at once.
ComplexityO(32) = O(1) time, O(1) space — Exactly 32 iterations of constant-time bit logic, independent of the inputs → O(1) time and O(1) space.
E · Edge cases and pitfalls5a = 0, b = 0 — Every column produces sum 0, carry 0 → result 0.Explore edge casesHide edge cases
Edge cases handled
a = 0, b = 0Every column produces sum 0, carry 0 → result 0.a = -2, b = 3Carries propagate through the sign bit; in Python bit 31 is set so the conversion yields 1.
Pitfalls
- In Python, forgetting the final sign conversion — a negative answer comes back as a large positive (e.g. 4294967295 instead of −1).
- Getting the carry logic wrong — it's the majority of three bits, not just bitA & bitB.
- Looping fewer than 32 times and dropping the sign bit at position 31.
Approach 2 of 2 · Optimal
XOR Sum + Carry Loop (Optimal)
1Hint 1Explore hintHide hint
Add 5 + 3 in your head ignoring carries column by column, then add the carries separately. Which bit op gives the carry-less sum, and which gives the carries?
2Hint 2Explore hintHide hint
a ^ b is the sum with every carry dropped. The positions that should have carried are exactly where both bits were 1: (a & b), shifted left by one.
3Hint 3Explore hintHide hint
Set a = a ^ b and b = (a & b) << 1, then repeat: keep folding the carry back in until there's no carry left (b == 0).
A · Core idea
Split addition into two halves and iterate. a ^ b is the sum if you forget to carry; (a & b) << 1 is precisely the carries you forgot, relocated to the column they belong in. Add those carries to the partial sum and repeat until there are no carries left.
Why `a ^ b` is the carry-less sum. Column by column, 0 + 0 = 0, 0 + 1 = 1, 1 + 0 = 1, and 1 + 1 = 0 with a carry. Ignoring the carry, that truth table is exactly XOR. So a ^ b is correct in every column where the two bits don't both equal 1.
Why `(a & b) << 1` is the carry. A column generates a carry only when both bits are 1 — that's a & b. And a carry always lands in the next column to the left, which is a left shift by one. So (a & b) << 1 is the complete set of carries, already positioned. Adding it back to a ^ b corrects every column XOR got wrong.
Why the loop terminates. Each iteration's carry sits strictly to the left of the bits that produced it, so the carries march toward the high end and eventually fall off the top of the fixed width — at which point b (the carry) is 0 and a holds the answer. For 32-bit values this is at most ~32 passes.
Why Python needs masking. Python ints are arbitrary precision, so (a & b) << 1 keeps growing and a negative input's carry never clears — the loop spins forever. Masking each step with & 0xFFFFFFFF confines the values to 32 bits so carries fall off as they would in a register. At the end, if bit 31 is set the pattern represents a negative number, which we recover with ~(a ^ 0xFFFFFFFF). Java needs none of this: its int already overflows at 32 bits.
B · Visual dry run
Interactive dry run
Select a frame to connect the decision with its visual state.
a = 2 (10), b = 3 (11)Interactive diagram
Carry folding until it clears
pass 1Each pass replaces (a, b) with (sum-without-carry, shifted carry) until the carry is 0.
5C · Code with teaching comments
D · Why it works and complexityO(1) timeO(1) spaceOpen the invariant and proofExplore the proofHide the proof
This is the full-adder from the previous approach collapsed into two parallel bitwise ops: XOR computes all 32 sum bits simultaneously, and AND-shift computes all 32 carries simultaneously. Re-feeding the carry is just 'add again with the leftovers' — the same way you'd hand-add 99 + 1 in two passes (sum digits, then propagate the carry).
ComplexityO(1) time, O(1) space — Each pass moves the carries at least one bit position left; within a fixed 32-bit width they clear after at most ~32 passes → O(1) time and O(1) space.
E · Edge cases and pitfalls5a = 0, b = 0 — b is already 0, loop never runs → returns 0.Explore edge casesHide edge cases
Edge cases handled
a = 0, b = 0b is already 0, loop never runs → returns 0.a = -1, b = 1Carries propagate left through all 32 bits and fall off; masking lets b & mask reach 0 → returns 0. Without masking Python spins forever.
Pitfalls
- Omitting the mask in Python — negative inputs make (a & b) << 1 grow without bound and the loop never terminates.
- Returning a & mask directly in Python without the sign conversion — negative answers come back as large positives.
- Using `>>` instead of `<<` for the carry — the carry must move LEFT into the next-higher column.
Practice
Try the solution yourself
Edit the optimal implementation, test another input, and observe the result.
Editable code previewpublic int getSum(int a, int b) { while (b != 0) { int carry = (a & b) << 1; a = a ^ b; b = carry;Explore the playgroundClose the playground
Avoid mistakes
Recognize the interview traps
Understand why common attempts fail before reviewing the corrected implementation.
1No masking in Python (infinite loop)
Python ints are arbitrary-precision, so a negative input's carry keeps growing instead of overflowing away — the loop's exit condition b == 0 is never met.
Explore the code comparisonHide the code comparison
No masking in Python (infinite loop)
Python ints are arbitrary-precision, so a negative input's carry keeps growing instead of overflowing away — the loop's exit condition b == 0 is never met.
Don't write this
while b != 0: # never terminates for negative inputs
carry = (a & b) << 1
a = a ^ b
b = carry
return aWrite this instead
mask = 0xFFFFFFFF
while (b & mask) != 0: # only the low 32 bits gate the loop
carry = (a & b) << 1
a = a ^ b
b = carry
a &= mask
return a if a <= 0x7FFFFFFF else ~(a ^ mask)2Returning the unsigned pattern instead of a signed value
After masking, a result with bit 31 set is the two's-complement encoding of a negative number. Returning a & mask as-is yields a large positive (e.g. 4294967295) instead of −1.
Explore the code comparisonHide the code comparison
Returning the unsigned pattern instead of a signed value
After masking, a result with bit 31 set is the two's-complement encoding of a negative number. Returning a & mask as-is yields a large positive (e.g. 4294967295) instead of −1.
Don't write this
a &= 0xFFFFFFFF
return a # -1 comes back as 4294967295Write this instead
a &= 0xFFFFFFFF
return a if a <= 0x7FFFFFFF else ~(a ^ 0xFFFFFFFF) # convert to signedRevise
Carry the pattern into the interview
Pattern to remember
Bitwise full-adder (XOR sum + carry loop)
Code pattern to memorize
while b != 0:
carry = (a & b) << 1 # bits that carry into the next column
a = a ^ b # add without carrying
b = carry # now add the carry in
return aRules to remember
- 1
a ^ bis sum without carry — it's correct in every column where at most one bit is set. - 2
(a & b) << 1is the carry: a column carries only when both bits are 1, and a carry lands one column to the left. - 3Loop until the carry (
b) is 0 — each pass pushes carries leftward, and they must eventually run off the top. - 4In Java,
intwraps at 32 bits for free. In Python, mask every step with `& 0xFFFFFFFF` and convert the high-bit-set result back to a negative via~(a ^ 0xFFFFFFFF). - 5Subtraction reuses the same machine:
a - b = a + (~b + 1)(two's complement negation).
Use this pattern when
- Add/subtract integers without the + or − operators
- Implement arithmetic from logic gates / simulate a full adder
- Hardware or constrained-instruction-set style questions
- Any 'do arithmetic with only bitwise ops' framing
Choose another pattern when
- You're allowed to use + → just use it; this trick is only for the artificial constraint
- Floating-point or arbitrary-precision addition → the 32-bit bit model doesn't apply
- Multiplication/division without operators → different shift-and-add structure
- You need overflow to throw rather than wrap → this silently wraps like hardware
Interview takeaway
Sum of Two Integers teaches that addition IS two bit operations: XOR for the digit, AND-shifted for the carry — repeated until no carry remains, exactly like a row of full adders. The real interview test is Python's unbounded ints: without `& 0xFFFFFFFF` masking and sign conversion, negative results never terminate or come out wrong.
Continue
Transfer the pattern to another problem
Use a direct variation or pattern sibling to prove the idea is reusable.
Transferable patternBitwise full-adder. Recognise it whenever you must do arithmetic without the arithmetic operators. XOR is the carry-less sum, (a & b) << 1 is the carry, and you loop until the carry clears — the deeper lesson being fixed-width two's-complement emulation, which Python forces you to spell out with & 0xFFFFFFFF.
Practice queueDirect variations and pattern siblings
Direct follow-ups
- Add BinarySame carry logic on binary strings instead of ints — XOR digit, carry the AND, build the string.
- Add Two NumbersComing soonDigit-by-digit addition on linked lists with a carry — the decimal analogue of this carry loop.
- Reverse BitsAnother fixed-width problem where Python needs & 0xFFFFFFFF and unsigned care.
- Divide Two IntegersComing soonDivision without / or *, via repeated shift-and-subtract — same 'arithmetic from primitives' spirit.