1Understand
The idea
x ^ x == 0 and x ^ 0 == x, so XOR-ing everything together cancels the pairs and leaves the odd one out. x & (x, 1) clears the lowest set bit, x & −x isolates it, and 1 << i builds a mask for bit i. Python integers have no fixed width, so mask with & 0xFFFFFFFF when a problem assumes 32 bits.
Intuition
Bits pack set-membership and parity into word operations. x ^ x == 0 and x ^ 0 == x, so XOR-ing a list cancels pairs and leaves the odd-one-out. x & (x - 1) clears the lowest set bit; x & -x isolates it; 1 << i builds a mask.
Python integers have unlimited width, mask with & 0xFFFFFFFF (and careful signing) when a problem assumes 32-bit overflow behaviour.
Prefer bit tricks when the problem mentions unique elements, subsets of a small universe, or constant-space constraints.
What you will be able to do
- Use XOR to cancel pairs
- Test, set and clear bits
When to use it
- Every element appears twice except one
- Count set bits
- Power of two, subsets as integers
2See it
Walkthrough
XOR finds the single
nums = [2, 3, 2], x^x=0, x^0=x.
1 / 5
acc = 0 identity for XOR.
Live template
Line 1 active
Complexity: time O(n) or O(bits), space O(1)
XOR scan is O(n) time, O(1) space, better than a hash set O(n) space. Bit DP over masks is O(2ⁿ · poly). Remember Python's unbounded ints when porting 32-bit puzzles.
Read the walkthrough as text
Single number. nums = [4,1,2,1,2].
- Start
x = 0. - XOR each value: pairs
1and2cancel. - Left with
4.
In code:
x = 0for v in nums:x ^= vreturn x
Count set bits: loop while n: n &= n - 1; count += 1, Brian Kernighan, O(#set bits).
3Recognise it
Kinds of problems (6)
Same pattern, different surfaces. Each row is a problem shape you should recognise, not only the first walkthrough example.
Single number (XOR)
Example. Every element twice except one, find unique.
How. XOR entire array; pairs cancel to 0.
Counting bits
Example. Count set bits 0..n.
How. dp[i] = dp[i>>1] + (i&1) or Brian Kernighan popcount in loop.
Power of two
Example. Is n a power of 2?
How. n > 0 and n & (n-1) == 0.
Reverse bits
Example. Reverse 32-bit representation of n.
How. Shift result left; add n&1; shift n right, repeat for width.
Sum without + (carry with AND/shift)
Example. Add integers without arithmetic +.
How. sum = a^b, carry = (a&b)<<1 until carry is 0.
Subsets as bitmasks
Example. Enumerate all subsets via for mask in range(1<<n).
How. mask indexes include set; test bit i with mask & (1<<i).
Common mistakes
Failure modes the tutor watches for. Open the Common mistake tab in the walkthrough to watch one fail live.
Negative numbers
Why it happens. 32-bit reverse-bit tricks assume fixed width.
How it fails. Reverse bits of Python -1 without mask, infinite sign bits, wrong length.
Fix. Mask to width (`& 0xFFFFFFFF`) when emulating fixed-width problems.
Operator precedence
Why it happens. `x & 1 == 0` reads like testing low bit.
How it fails. Parses as x & (1 == 0) → x & 0, always false.
Fix. Use `(x & 1) == 0` or `x & 1 == 0` with parens on `&`.
Shift direction
Why it happens. Left vs right shift is easy to invert when building masks.
How it fails. Build high-bit mask with shift right instead of left, wrong bits set.
Fix. 1 << k sets bit k; >> clears toward LSB, double-check mask direction.
4Check yourself
Concept check
A short quiz on this lesson before you practise. Optional, and it does not gate coding.
Ready to practise?
Mastery comes from solving. The lesson is optional context.