Skip to content
Tutorials Center
My learning

Topics

Lesson 24 of 63 ยท Math for Contests

Bit Tricks and XOR Problems

Bitmask basics, subset enumeration in 3^n, XOR identities, prefix XOR counting, maximum XOR pair and the linear basis idea, with tested Python examples.

Bits are the contest programmer's favorite compression. A set of up to 20 items fits in one integer, a yes/no table over those items becomes a list indexed by that integer, and a pile of unrelated-looking XOR statements often collapse into a few identities. The mechanics of &, |, ^ and shifts are covered in Bit Manipulation; this lesson is about the patterns that actually appear in problems.

We will cover masks as sets, enumerating subsets and submasks (and why the cost is 3^n, not 4^n), the XOR identities that solve "find the odd one out" and "count subarrays" problems, the maximum XOR pair, and the idea of a linear basis for "what values can I make by XOR-ing some of these numbers?"

Masks as sets

An integer from 0 to 2^n - 1 represents a subset of {0, ..., n-1}: bit i is 1 when item i is present. Python integers are unbounded, so there is no sign or width trouble, but for anything above about n = 22 the table of 2^n states stops fitting in time or memory.

The operations you need every day:

Goal Expression
Test item i mask >> i & 1
Add item i mask | 1 << i
Remove item i mask & ~(1 << i)
Flip item i mask ^ 1 << i
Lowest set bit mask & -mask
Clear lowest set bit mask & (mask - 1)
Number of items mask.bit_count()
Union / intersection a | b, a & b
Is a a subset of b? a & b == a

int.bit_count() exists since Python 3.10 and is the fast popcount. mask & -mask isolates the lowest set bit as a value; .bit_length() - 1 of that gives its index.

Enumerating subsets and submasks

To list all subsets of an n-item set, loop mask from 0 to (1 << n) - 1. To list all submasks of a given mask (every subset of its set bits), use the classic walk:

Text
sub = mask
while True:
    process(sub)
    if sub == 0: break
    sub = (sub - 1) & mask

Subtracting one flips the lowest set bit and everything below it; AND-ing with mask throws away bits outside the set, so the walk visits each submask exactly once in decreasing order.

If you do this for every mask, the total number of (mask, submask) pairs is 3^n: each item is independently "not in mask", "in mask but not in sub", or "in both". That is why subset DPs of this form run for n up to about 15 or 16, but not 20.

flowchart TD
    A["Item i"] --> B["Not in mask"]
    A --> C["In mask, not in submask"]
    A --> D["In mask and in submask"]

Three states per item give 3^n pairs of a mask and its submask.

Python Masks, subset walks and the 3^n count

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

XOR identities

XOR is addition without carry, and a few facts carry most of its weight:

  • a ^ a == 0 and a ^ 0 == a, so XOR-ing a value twice cancels it.
  • It is commutative and associative, so the order in which you combine values does not matter.
  • If a ^ b == c then a ^ c == b and b ^ c == a: any one of the three can be recovered from the other two.
  • XOR of 0..n follows a period of four: it equals n, 1, n + 1, 0 when n % 4 is 0, 1, 2, 3.

The first group gives the "odd one out" trick: if every number appears twice except one, the XOR of the whole array is that one number, in O(n) time and O(1) memory.

The same cancellation gives prefix XOR. Let P[i] be the XOR of the first i elements. Then the XOR of the subarray a[l..r] is P[r+1] ^ P[l], because the shared prefix cancels. A subarray has XOR zero exactly when two prefix values are equal, and it has XOR k when P[r+1] ^ P[l] == k, that is P[l] == P[r+1] ^ k. Counting such pairs is the same dictionary pattern as "subarray with sum k", with XOR in place of subtraction (see Prefix Sums).

Python Odd one out, XOR 0..n and counting subarrays

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Addition and bit-operation identities

XOR is addition without carry, and AND finds exactly the positions that produce a carry. That gives a family of identities that turn arithmetic into bit operations and back:

  • a + b == (a ^ b) + 2 * (a & b): the sum without carries, plus the carries shifted one place to the left.
  • a + b == (a | b) + (a & b): OR counts every set position once, AND adds back the positions where both are set.
  • a | b == (a ^ b) + (a & b), which is a | b == (a ^ b) | (a & b) too, because the two parts never overlap.
  • a ^ b == (a | b) - (a & b).
  • a ^ (a & b) == (a | b) ^ b: both sides are the bits of a that are not in b.
  • (a & b) ^ (a | b) == a ^ b.

They matter in problems that fix a sum or an OR and ask about the rest. For example, if a + b = s and a ^ b = x, then a & b = (s - x) / 2 (it must be a non-negative integer, and x & ((s - x) / 2) must be 0).

Common one-line manipulations, with x a non-negative integer and i a bit index counted from 0:

Goal Expression
Set bit i x | (1 << i)
Unset (clear) bit i x & ~(1 << i)
Toggle bit i x ^ (1 << i)
Test bit i (x >> i) & 1
Clear bits from the most significant bit down to i x & ((1 << i) - 1)
Clear bits from i down to bit 0 x & ~((1 << (i + 1)) - 1)
Invert the lowest n bits (one's complement within n bits) x ^ ((1 << n) - 1)
Is x a power of two? x > 0 and x & (x - 1) == 0
Highest set bit as a value 1 << (x.bit_length() - 1)
Count set bits x.bit_count() (Python 3.10+)
Divide or multiply by 2**i x >> i, x << i

The loop behind x & (x - 1) is Brian Kernighan's algorithm: each iteration removes the lowest set bit, so counting the set bits takes one step per set bit instead of one per bit position.

Python Checking the identities and one-liners by brute force

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Maximum XOR of two numbers

Given an array, choose two elements whose XOR is as large as possible. Trying all pairs is O(n^2). The greedy bit-by-bit approach is O(n * B) with B bits: decide the answer from the top bit down. At each bit, hope the answer has this bit set; look at the set of all numbers truncated to the bits decided so far (their prefixes). The hope is achievable when some pair of prefixes XORs to the candidate answer, which is a single set lookup per element, because p ^ candidate must itself be a prefix.

This is the same job a binary trie does. The set version is shorter to type, which matters in a contest.

The linear basis idea

Now the opposite question: given numbers a1..an, which values can you make by XOR-ing some of them? The set of reachable values is a vector space over the two-element field, and you can describe all of it by a basis of at most B numbers (B is the bit width).

Build the basis by inserting numbers one at a time into slots basis[b], where slot b holds a value whose highest set bit is b. To insert x, scan bits from high to low: if the bit is set and its slot is empty, store x there and stop; if the slot is full, replace x by x ^ basis[b] and continue. If x becomes zero, it was already reachable, and the basis is unchanged.

From a basis you get a lot:

  • The number of distinct reachable values is 2^rank, where rank is the number of non-empty slots.
  • The maximum reachable value comes from a greedy pass from high bits to low: take res ^ basis[b] whenever it increases res.
  • A value v is reachable exactly when reducing it with the basis ends at zero.
Python Maximum XOR pair and a linear basis

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Pitfalls

  • Operator precedence in Python: &, ^, | bind looser than == in many languages, but in Python comparison binds looser than bitwise operators, so mask >> i & 1 works. Even so, parenthesize when mixing shifts with + or -, since + binds tighter than <<: 1 << i + 1 is 1 << (i + 1).
  • ~x is -x - 1 for Python integers; use x ^ full with an explicit full mask ((1 << n) - 1) when you want the complement within n bits.
  • Negative numbers behave as if they had infinitely many leading ones. x & -x still works; a right shift of a negative number keeps the sign.
  • A DP over 2^n masks with n = 20 is a million states. In Python that is fine if each step is cheap, and too slow if each state loops over 20 items inside nested function calls. Estimate first (see Estimating Time and Memory).

Bitwise operations over ranges

AND, OR and XOR act on every bit independently. That one fact solves a whole class of range problems: split the problem into one question per bit, answer each with a prefix sum, and recombine.

  • AND of a range: bit b is set in the answer only if every element has it. With a prefix count of elements having bit b, check count == length.
  • OR of a range: bit b is set if at least one element has it: count > 0.
  • XOR of a range: bit b is set if the count of elements having it is odd. (A single prefix XOR array is simpler for this one.)
  • Sum of a[i] ^ a[j] over all pairs in a range: each bit contributes 2^b * ones * zeros, because a pair differs in bit b exactly when one element has it and the other does not.
  • Sum of the XOR of all subarrays: a subarray XOR is P[r+1] ^ P[l] for prefix XORs P, so you need the sum of P[i] ^ P[j] over all pairs of prefix values. The per-bit pair formula applies again, with n + 1 prefix values.
  • Largest XOR of any subarray: you need the best pair of prefix XORs. The set-based trick in the section above works for one bit at a time; a binary trie answers "which stored number maximizes XOR with x" by walking from the top bit and preferring the opposite bit whenever it exists.

Each of the per-bit tables uses B arrays of length n + 1 (about 20 to 30 arrays), so memory is B * n integers. That is fine for n = 10^5 and a good reason to know the trie alternative, which uses n * B nodes but answers each query in O(B).

Python Per-bit prefix sums and an XOR trie

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

All three structures are compared against loops over every subarray or pair, so a miscounted bit would fail an assert instead of silently printing a wrong total.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. Which expression tests whether item i is in the set represented by mask?

    Shifting the mask right by i puts bit i in position zero, and & 1 keeps only that bit.
  2. 2. Summed over every mask of an n-item set, how many (mask, submask) pairs are there?

    Each item is independently outside the mask, in the mask but not the submask, or in both. Three choices per item give 3^n.
  3. 3. All numbers in an array appear twice except one. How do you find it in O(n) time and O(1) extra memory?

    Equal pairs cancel (a ^ a = 0) and zero is neutral, so only the single number remains.
  4. 4. A linear basis for a list of numbers has rank 5. How many distinct values can be formed as the XOR of some subset (including the empty subset)?

    Each of the five basis vectors is either used or not, and the choices give distinct results, so there are 2^5 = 32 values.
  5. 5. With prefix XOR P, how do you get the XOR of a[l..r]?

    P[r + 1] contains a[0..r] and P[l] contains a[0..l-1]. XOR-ing them cancels the shared part and leaves a[l..r].

Summary

  • A bitmask is a set; learn the one-line operations for test, add, remove, flip, lowbit and popcount.
  • Walk all submasks with sub = (sub - 1) & mask; doing it for every mask costs 3^n.
  • XOR cancels equal values, so it finds odd one out, turns subarray XOR into a difference of prefixes, and has the O(1) 0..n formula.
  • The maximum XOR pair is decided bit by bit with a set of prefixes (or a trie).
  • A linear basis of at most B numbers describes every XOR-reachable value: 2^rank of them, with a greedy maximum.
  • Treat each bit separately: per-bit prefix counts give range AND/OR and pair-XOR sums; a binary trie finds the maximum XOR.

Next: Prefix Sums and Difference Arrays