XOR and Arithmetic

What is this?

XOR is a light switch with a memory quirk — flip it with the same value twice and it returns to where it started, so pairs cancel out and only the odd one left over survives. Building on that, you can even rebuild grade-school addition and division using nothing but switch operations. These problems lean on that self-cancelling trick and switch-by-switch math.

💡 Fun fact: The self-cancelling nature of XOR powers the classic in-place swap of two variables without a temporary, and it is the same property that lets RAID disk arrays rebuild a lost drive from the others.

🔓 The 4 problems in this chapter are free. Sign in with Google or Microsoft to start solving.

Core idea: XOR cancels equal pairs to zero, so XOR-ing matched values leaves the odd one out. Push that idea further and you can rebuild arithmetic itself — addition becomes XOR for the sum plus a shifted AND for the carry, and division becomes repeated shift-and-subtract.

The pattern

XOR's defining property is a ^ a == 0 and a ^ 0 == a. XOR a stream of numbers where everything appears in pairs and the pairs annihilate, leaving only the unpaired survivor. The same logic pairs indices against values: XOR all indices 0..n together with all array entries, and every matched index/value cancels, exposing the missing one.

The arithmetic problems strip operators down to gates. Addition without +: a ^ b gives the sum ignoring carries, (a & b) << 1 gives the carries, and you repeat until the carry is zero. Division without /: subtract the largest left-shifted multiple of the divisor you can, accumulating the corresponding power of two into the quotient — long division in base two. Reasoning about how few bit operations reach a target leans on the same shift-and-count instinct.

The problems

• Missing Number — XOR every index 0..n with every value; matched pairs cancel and the gap remains.
• Sum of Two Integers — add without +: XOR for the partial sum, shifted AND for the carry, loop until no carry.
• Divide Two Integers — shift-subtract long division; peel off the biggest shifted divisor and add its power of two to the quotient.
• Minimum Operations to Make the Integer Zero — reason from set-bit counts about how many shift/subtract steps are required.

Key takeaways

1. a ^ a == 0 makes XOR a self-canceling accumulator — perfect for isolating an unpaired element.
2. XOR indices against values to surface a missing number in linear time and constant space.
3. Addition decomposes into XOR (sum) plus shifted AND (carry), iterated until the carry clears.
4. Division is shift-and-subtract: remove the largest shifted divisor and record its power of two.
5. Watch sign and overflow boundaries when rebuilding arithmetic on fixed-width signed integers.