Bit manipulation and bitmask state · HTML
XOR obeys x^x=0, x^0=x, commutativity, and associativity; AND/OR manage bit sets and (x>>b)&1 reads bit b.
Recognition signals
- Paired values should cancel
- Only occurrence parity matters
- Hamming distance or per-bit contribution appears
- One value is missing or unique
- State separates into fixed-width independent bits
False friends
| Signal | Why it is different |
|---|
| Frequency beyond parity is needed | One XOR retains only parity; use a frequency map or modular bit counts. |
| Assuming fixed-width negative Python integers | Python uses infinite sign extension, so two's-complement tasks need an explicit mask. |
Core invariant
The running XOR equals the XOR of values with odd processed frequency; per-bit counts can be reduced independently modulo a repetition count.
State, transition, and processing order
| Item | Definition |
|---|
| State | An XOR accumulator or W bit counters, plus an explicit full-width mask when needed. |
| Transition | For each x, apply acc^=x or add (x>>b)&1 to each bit counter. |
| Frontier / order | Processed values are compressed into a bit summary; commutativity makes their internal order irrelevant. |
Python skeleton
def single_among_pairs(values):
ans = 0
for x in values:
ans ^= x
return ans
def hamming_distance(a, b):
return (a ^ b).bit_count()
def unsigned_low_bits(x, width):
return x & ((1 << width) - 1)
Correctness sketch
- Commutativity and associativity permit arbitrary XOR regrouping.
- Each equal pair cancels to zero.
- Zero leaves the unpaired value unchanged, so it is the final accumulator.
- Set bits of a^b are exactly positions where a and b differ.
Complexity
| Time | Space | Parameters |
|---|
| O(n) for XOR aggregation or O(nW) for per-bit counting | O(1) or O(W) | n values and chosen bit width W |
Edge cases
- An empty XOR is zero but may have no problem meaning
- Negative values require a width
- Parenthesize shifts and masks
- The occurrence rule must match the modulus
- Overflow and sign-bit behavior vary by language
Error patterns
| Pattern | Why it fails / fix |
|---|
| Treating XOR as addition | XOR carries neither arithmetic carries nor magnitude. |
| Applying a uniqueness trick without its frequency premise | A different repetition pattern leaves a mixture of values. |
| Ignoring sign extension | Right shifts and complement on negatives must be width-limited. |
Selection and exclusion rules
- Everything paired except one: XOR.
- Each bit contributes independently: per-bit counting.
- Exact frequencies are required: hash map.
- For signed two's complement output, mask and convert the sign bit explicitly.
Original micro-example
| Part | Detail |
|---|
| Result | The XOR result is 9. |
| Scenario | Sequence [12,5,12,9,5]. |
| Walkthrough | The two 12s and two 5s cancel independently, leaving 9. |
Recall prompts
My notes