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
ANDfor 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..nwith every value; matched pairs cancel and the gap remains. - Sum of Two Integers — add without
+: XOR for the partial sum, shiftedANDfor 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
a ^ a == 0makes XOR a self-canceling accumulator — perfect for isolating an unpaired element.- XOR indices against values to surface a missing number in linear time and constant space.
- Addition decomposes into XOR (sum) plus shifted AND (carry), iterated until the carry clears.
- Division is shift-and-subtract: remove the largest shifted divisor and record its power of two.
- Watch sign and overflow boundaries when rebuilding arithmetic on fixed-width signed integers.
Core idea: After
koperations you've removed exactlyk * num2plus a sum ofkpowers of two — sokworks if and only ifpopcount(num1 - k*num2) <= k <= num1 - k*num2. Tryk = 1, 2, 3, ...and return the first one that fits.
Problem, rephrased
You manage a budget meter that currently reads num1. You can press a "discharge" button as many times as you like. Each press does two things at once:
- it lets you choose one power-of-two amount
2^i(anyifrom 0 to 60) to drain, and - it applies a fixed surcharge
num2that is added to whatever you drain (so the meter changes by2^i + num2).
Every press subtracts 2^i + num2 from the meter. Your goal: get the meter to read exactly 0 in the fewest presses possible. If no number of presses can ever land precisely on 0, report -1.
The surcharge num2 can be negative (it secretly gives you budget back each press) or positive (it costs you extra each press). That sign is the whole drama.
num1 |
num2 |
Answer | Why |
|---|---|---|---|
| 3 | -2 | 3 | 3 presses can be arranged to hit 0 exactly |
| 5 | 7 | -1 | every press removes too much; you overshoot before reaching 0 |
Sign in to continue reading
The rest of this lesson is available with a free account. Signing in with Google or Microsoft is free.
Sign in to read the full lesson