Understand
30-second explanation
Build the interview-ready mental model before comparing implementations.
Count the integers x in [0, n] with n + x == n ^ x. Addition equals XOR exactly when there are no carries, which happens precisely when n & x == 0 — x may only set bits where n has a 0. So x is any subset of n's zero-bit positions, giving 2^(number of zero bits in n) values. Counting the zero bits is O(log n).
Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview contextHide interview context
What's being tested
Whether you know addition decomposes into XOR plus carries, can deduce that n + x == n ^ x means n & x == 0, and then count the free (zero) bit positions to get 2^zeros instead of iterating to n.
Where candidates slip
Brute-forcing all x in [0, n] (O(n), too slow for large n), or counting zero bits including positions above n's most significant bit and overcounting.
How to stand out
Derive the carry identity on the board, conclude n & x == 0, and explain why each zero bit of n is an independent binary choice giving 2^(zero bits) — an O(log n) bit count.
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 previewCount x in [0,n] with n+x == n^xUse the carry identity?NoYesExplore 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
Brute Force — Test Every x
1Hint 1Explore hintHide hint
Directly count: loop x from 0 to n and check whether n + x equals n ^ x.
2Hint 2Explore hintHide hint
Each check is O(1); the loop runs n + 1 times.
3Hint 3Explore hintHide hint
Correct, but for n up to 10¹⁵ this is far too slow — it motivates finding the closed form.
A · Core idea
The literal reading: enumerate every candidate and test the condition.
The loop. For each x in [0, n], compute n + x and n ^ x and increment a counter when they match. This is unambiguously correct and easy to reason about.
Where it breaks. With n as large as 10¹⁵, iterating up to n is hopeless — it would take on the order of a quadrillion iterations. The brute force exists only to confirm what the condition means and to give the optimal solution something to validate against on small inputs.
The bridge to the optimal. Run the brute force on a small n and look at which x pass. For n = 5 (101) the passing values are 0 and 2 — exactly the numbers whose bits sit only in n's zero position. That observation, that the passing x are the ones sharing no 1-bit with n, is the doorway to the closed form.
B · Visual dry run
Interactive dry run
Select a frame to connect the decision with its visual state.
n = 5Interactive diagram
Which x pass for n = 5
x=0Only x = 0 and x = 2 pass — precisely the values with bits in n's zero position.
2C · Code with teaching comments
Reference implementation previewpublic long sumXor(long n) { long count = 0; for (long x = 0; x <= n; x++) { if (n + x == (n ^ x)) { count++;Explore the full codeHide the full code
D · Why it works and complexityO(n) timeO(1) spaceOpen the invariant and proofExplore the proofHide the proof
The brute force's passing values always have no 1-bit in common with n. Spotting that pattern — n & x == 0 — converts an O(n) scan into a bit count.
ComplexityO(n) time, O(1) space — The loop runs n + 1 times with constant work per iteration, so O(n) time and O(1) space — infeasible for large n.
E · Edge cases and pitfalls3Running this for large n — O(n) is far too slow at n up to 10¹⁵.Explore edge casesHide edge cases
Pitfalls
- Running this for large n — O(n) is far too slow at n up to 10¹⁵.
- Forgetting operator precedence: write (n ^ x) in parentheses so it isn't compared before XOR.
- Using a 32-bit int for n or the count and overflowing.
Approach 2 of 2 · Optimal
Count Zero Bits — 2^zeros (Optimal)
1Hint 1Explore hintHide hint
Recall a + b = (a ^ b) + ((a & b) << 1). When is the second term zero? That tells you exactly when n + x == n ^ x.
2Hint 2Explore hintHide hint
n + x == n ^ x iff n & x == 0, i.e. x has 1-bits only where n has 0-bits.
3Hint 3Explore hintHide hint
Each zero bit of n (up to its most significant set bit) is an independent yes/no for x. So the count is 2 raised to the number of those zero bits.
A · Core idea
Turn the condition into a bit count using how addition really works.
The carry identity. For any two integers, a + b = (a ^ b) + ((a & b) << 1). The XOR is the sum of bits ignoring carries; a & b marks the positions where both have a 1 and therefore carry into the next position, and the << 1 performs that carry. So addition and XOR agree precisely when the carry term a & b is zero.
Applying it to n and x. Setting a = n, b = x, the equation n + x == n ^ x holds if and only if n & x == 0. In words: x is allowed to have a 1-bit only in positions where n has a 0-bit. Wherever n already has a 1, x must have a 0 there, or a carry would break the equality.
Counting the valid x. Look at the binary form of n. Every position where n is 0 is a free slot: x may put a 1 there or not, independently of the other slots. With z such zero positions there are 2^z ways to choose, and each gives a distinct valid x. Crucially, you only count zero bits at or below n's most significant set bit — a 1 above that would push x past n and out of range.
Why x ≤ n is automatically satisfied. Any x built from n's lower zero positions is strictly smaller than n at the first differing high bit (n has a 1 where x has 0 somewhere above), so every counted x lands in [0, n]. The single exception is x = 0 (the empty choice), always valid.
The n = 0 edge. Zero has no set bits and no zero bits below an MSB, so there are no free slots — 2^0 = 1, matching the lone valid x = 0.
B · Visual dry run
Interactive dry run
Select a frame to connect the decision with its visual state.
n = 10 (binary 1010)Interactive diagram
Zero bits are the free choices
bit 0For n = 1010, the two zero positions each double the count: 2^2 = 4.
4C · Code with teaching comments
D · Why it works and complexityO(log n) timeO(1) spaceOpen the invariant and proofExplore the proofHide the proof
Sum equals XOR exactly when bits don't collide, and 'don't collide with n' means 'live in n's zero bits'. Independent binary choices over those z zero bits give 2^z — the whole problem is counting zeros in n's binary form.
ComplexityO(log n) time, O(1) space — Counting the zero bits of n scans about log₂(n) bit positions, then a single shift produces 2^zeros — O(log n) time, O(1) space.
E · Edge cases and pitfalls6n = 0 — Special-cased to 1: only x = 0 satisfies 0 + 0 == 0 ^ 0.Explore edge casesHide edge cases
Edge cases handled
n = 0Special-cased to 1: only x = 0 satisfies 0 + 0 == 0 ^ 0.n = 7 (111)No zero bits below the MSB → 2^0 = 1. Only x = 0 works; every other x collides.n = 8 (1000)Three zero bits below the MSB → 2^3 = 8. x ranges over all subsets of the low three positions.
Pitfalls
- Counting zero bits above n's most significant set bit — those x would exceed n.
- Forgetting the n = 0 case, where the while loop never runs.
- Using 1 << zeros on a 32-bit int in Java for large counts — use 1L << zeros.
Practice
Try the solution yourself
Edit the optimal implementation, test another input, and observe the result.
Editable code previewpublic long sumXor(long n) { if (n == 0) { return 1; // only x = 0 works } int zeros = 0;Explore the playgroundClose the playground
Avoid mistakes
Recognize the interview traps
Understand why common attempts fail before reviewing the corrected implementation.
1O(n) brute force on large n
n can be 10¹⁵; iterating every x is astronomically slow. The carry identity gives an O(log n) count.
Explore the code comparisonHide the code comparison
O(n) brute force on large n
n can be 10¹⁵; iterating every x is astronomically slow. The carry identity gives an O(log n) count.
Don't write this
return sum(1 for x in range(n + 1) if n + x == (n ^ x)) # O(n)Write this instead
zeros = bin(n).count('0') - 1 if n else 0 # zeros below MSB
return 1 << zeros2Counting zero bits above the MSB
Only zero bits at or below n's highest set bit are free; higher 1s in x would make x > n.
Explore the code comparisonHide the code comparison
Counting zero bits above the MSB
Only zero bits at or below n's highest set bit are free; higher 1s in x would make x > n.
Don't write this
int zeros = 0;
for (int i = 0; i < 64; i++) if (((n >> i) & 1) == 0) zeros++; // counts high zeros tooWrite this instead
int zeros = 0;
while (n > 0) { if ((n & 1) == 0) zeros++; n >>= 1; } // stops at the MSB3Missing n = 0
When n is 0 the while loop body never executes; without a guard you might return 0 instead of the correct 1.
Explore the code comparisonHide the code comparison
Missing n = 0
When n is 0 the while loop body never executes; without a guard you might return 0 instead of the correct 1.
Don't write this
int zeros = 0;
while (n > 0) { ... }
return 1L << zeros; // returns 1 here by luck, but be explicitWrite this instead
if (n == 0) return 1;
// then count zero bitsRevise
Carry the pattern into the interview
Pattern to remember
n + x == n ^ x ⇔ n & x == 0 ⇒ 2^(zero bits of n)
Code pattern to memorize
if n == 0: return 1
zeros = count of 0-bits in n (up to its highest set bit)
return 1 << zeros # 2^zerosRules to remember
- 1Addition = XOR + carries.
a + b = (a ^ b) + ((a & b) << 1). They're equal iff the carry terma & bis 0. - 2So
n + x == n ^ xiff `n & x == 0` — x can have 1-bits only where n has 0-bits. - 3Each of n's zero-bit positions is an independent free choice (set it in x or not), so the count is
2^(number of zero bits). - 4Count zero bits only up to n's most significant set bit — bits above it would make x > n and fall outside [0, n].
- 5n = 0 is a special case: only x = 0 works, so the answer is 1 (which
2^0gives if you count zero free bits).
Use this pattern when
- Relate addition and XOR via the carry term a & b
- Count values satisfying a no-overlapping-bits condition
- Turn a [0, n] search into counting subsets of zero-bit positions
- Any 'how many x make a + x == a ^ x' style question
Choose another pattern when
- x ranges beyond [0, n] with no bound tied to n's MSB → the subset count breaks
- The condition involves OR or shifts, not the carry identity → different reasoning
- n is huge and given as a bit string, not an int → count zeros directly from the string
- You need the actual x values, not the count → enumerate the subsets
Interview takeaway
The identity a + b = (a ^ b) + ((a & b) << 1) is the whole problem: sum equals XOR exactly when bits don't overlap. Then 'how many x' becomes 'how many subsets of n's zero bits' = 2^(zero-bit count) — counted in O(log n).
Continue
Transfer the pattern to another problem
Use a direct variation or pattern sibling to prove the idea is reusable.
Transferable patternCarry identity plus subset counting. Whenever addition and XOR are compared, recall a + b = (a ^ b) + ((a & b) << 1): they match iff bits don't overlap. 'How many x' then becomes 'how many subsets of the allowed bit positions', i.e. 2^(free bits). Sum of Two Integers uses the same identity to add without the + operator.
Practice queueDirect variations and pattern siblings
Direct follow-ups