Lesson 34.3 · Bit Manipulation
XOR Identities
x ^ x = 0, x ^ 0 = x, and XOR is commutative and associative, so XOR-ing a list cancels every value that appears an even number of times.
10 min
Think of it like this
A light switch that each person flips as they walk through a door. If everyone walks through twice, the light ends as it started. Only someone who passed an odd number of times changes it.
1.Cancelling pairs
Single Number: XOR everything; pairs cancel and the lone value remains. Missing Number (Module 2): XOR all indices and values. Two singles (Single Number III): the XOR of everything is a ^ b ≠ 0; any set bit of it splits the numbers into two groups with one single each.
Counting bits by position (Single Number II): for each of the 32 bit positions, count how many numbers have it set; counts not divisible by 3 come from the single value.
nums = [4, 1, 2, 1, 2]x(vars)
Step 1/3x = 0 ^ 4 = 4.
Remember
- Pairs cancel.
- a ^ b's set bits show where a and b differ.
- Per-bit counts for "appears k times".
Common mistakes
- Expecting XOR to find a value that appears three times among pairs (it doesn't).