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: Instead of subtracting the divisor one copy at a time, subtract the largest doubled multiple of it that still fits (
divisor << k), then add1 << kto the quotient — turning O(quotient) work into O(log quotient).
Problem, rephrased
You're writing firmware for a tiny microcontroller whose ALU has an adder, a comparator, and a barrel shifter — but no divide instruction and no multiply instruction. You need a routine that computes the integer quotient of two whole numbers using only addition, subtraction, comparison, and bit shifts.
Given a dividend and a non-zero divisor, return dividend // divisor truncated toward zero (so -7 / 2 is -3, not -4). Both inputs are 32-bit signed integers, and the answer must be clamped to the 32-bit signed range [-2^31, 2^31 - 1]. The only case that overflows is INT_MIN / -1 — that true answer is 2^31, which doesn't fit, so we return 2^31 - 1.
You may not use *, /, or % anywhere.
| dividend | divisor | quotient | why |
|---|---|---|---|
10 |
3 |
3 |
3*3 = 9 ≤ 10 < 12 |
43 |
8 |
5 |
5*8 = 40 ≤ 43 < 48 |
7 |
-3 |
-2 |
magnitude 2, signs differ → negative; truncates toward zero (not -3) |
-100 |
7 |
-14 |
magnitude 14, signs differ → negative |
5 |
9 |
0 |
dividend smaller than divisor |
-2147483648 |
-1 |
2147483647 |
overflow — true answer 2^31 clamps to INT_MAX |
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