Math & Bits

Bit Manipulation

XOR tricks, masks and bit counting.

Medium, about 75 minutes to practise.

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

i
2
3
2
012

acc = 0 identity for XOR.

acc = 0

Live template

Line 1 active

1x & (x - 1) # clear lowest set bit
2x & -x # lowest set bit
3a ^ a == 0 # XOR cancels pairs

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].

  1. Start x = 0.
  2. XOR each value: pairs 1 and 2 cancel.
  3. Left with 4.

In code:

  • x = 0
  • for v in nums:
  • x ^= v
  • return 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.

All lessons