Skip to content
Tutorials Center
My learning

Topics

Lesson 194 of 225 ยท Math and Bit Manipulation

Gray Code and Bit Tricks

Generate Gray code with i ^ (i >> 1), decode it, walk all subsets by flipping one bit at a time, enumerate submasks and use lowest-set-bit tricks in Python.

In Bit Manipulation you learned the basic operators: AND, OR, XOR, shifts and the classic masks. This lesson goes one step further with a famous sequence, the Gray code, and a small set of tricks that show up again and again in interview problems and in bitmask DP: walking through every subset of a set, walking through every submask of a mask, and isolating the lowest set bit.

A Gray code is an ordering of all n-bit numbers such that two consecutive numbers differ in exactly one bit. Ordinary binary counting does not have this property: going from 011 to 100 flips three bits at once. Gray code is used in rotary encoders (a sensor that must never read a "half-way" value), in Karnaugh maps, and in puzzles such as the Tower of Hanoi and the Chinese rings.

The formula: i ^ (i >> 1)

The i-th Gray code is obtained by XOR-ing i with itself shifted right by one:

Python
def gray(i: int) -> int:
    return i ^ (i >> 1)

Why does this work? Look at what happens when i increases by one. The trailing run of ones turns into zeros and the next zero turns into a one. After XOR-ing with the shifted copy, only the bit at the boundary of that change differs between neighbours. You do not need the proof to use it, but you can check it by running the code.

Python Gray code for 3 bits

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.

Notice that the sequence is cyclic: the last code (100) differs from the first (000) in one bit too.

Decoding: from Gray code back to the index

To go the other way you XOR together all right-shifts of the code. The loop below keeps folding the high bits down:

Python
def inverse_gray(g: int) -> int:
    n = 0
    while g:
        n ^= g
        g >>= 1
    return n

If g = i ^ (i >> 1), then g ^ (g >> 1) ^ (g >> 2) ^ ... telescopes back to i. Each step is O(1), so decoding costs O(log g).

The reflect-and-prefix construction

There is a second, more visual way to build the list, and it is the one most interviews ask about ("generate Gray code of n bits"). Take the list for n - 1 bits, reflect it (write it backwards), put a 0 in front of the original half and a 1 in front of the reflected half.

flowchart LR
    A["n = 1<br/>0, 1"] --> B["reflect:<br/>1, 0"]
    B --> C["prefix 0 and 1<br/>00, 01, 11, 10"]
    C --> D["n = 2 done<br/>repeat for n = 3"]

Doubling a Gray code list: original with a 0 prefix, then the mirror image with a 1 prefix.

The two halves meet at the mirror, where the last code of the first half and the first code of the second half are the same number, differing only in the new top bit.

Python Reflect and prefix, compared with the formula

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.

Both methods produce the same list. The formula is shorter and gives any single element in O(1); reflection is easier to explain.

Subsets by bitmask

A set with n elements has 2^n subsets. Represent a subset as an n-bit integer: bit j is set when element j is in the subset. Counting mask from 0 to 2^n - 1 visits every subset exactly once. This is the iterative cousin of the recursion in subsets and permutations.

If you visit the masks in Gray order instead, each step adds or removes exactly one element. That is useful when updating a running value is cheap but recomputing it is expensive (for example a running sum or a running XOR).

Python Subsets in Gray order with a running sum

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.

Each subset sum is updated in O(1) instead of re-adding up to n numbers, so enumerating all subsets costs O(2^n) overall rather than O(n * 2^n).

Enumerating all submasks of a mask

Often you only care about subsets of a given set mask. The trick below visits every submask in decreasing order and never wastes a step:

Python
sub = mask
while sub:
    # use sub
    sub = (sub - 1) & mask
# the empty submask (0) is not visited by this loop; handle it separately

Subtracting one flips the lowest set bit and turns the zeros below it into ones; AND-ing with mask throws away every bit that is not allowed. If you run this for every mask of n bits, the total work is 3^n (each element is in the mask and in the submask, in the mask only, or in neither), which is the cost behind many subset-DP solutions.

Python Submasks of a mask

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.

A mask with k set bits has exactly 2^k submasks, here 2^3 = 8.

Other tricks worth knowing

These one-liners reappear constantly:

  • Lowest set bit: x & -x. In two's complement, -x flips every bit above the lowest set bit, so the AND keeps only that bit. This is the engine of the Fenwick tree.
  • Clear the lowest set bit: x & (x - 1). Counting how many times you can do it gives the popcount (Brian Kernighan's method).
  • Power of two test: x > 0 and x & (x - 1) == 0.
  • Index of the lowest set bit: (x & -x).bit_length() - 1.
  • Swap without a temporary: a ^= b; b ^= a; a ^= b works, but in Python a, b = b, a is clearer and just as fast.
  • Next number with the same popcount (Gosper's hack): useful for iterating over all subsets of size exactly k.
Python Lowest bit tricks and Gosper's hack

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.

Gosper's hack walks through the C(4, 2) = 6 masks of exactly two set bits without looking at the other ten.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. What does the Gray code of i equal?

    XOR-ing a number with itself shifted right by one gives the Gray code, a sequence in which neighbours differ in exactly one bit.
  2. 2. How many submasks does a mask with 4 set bits have, counting 0 and the mask itself?

    Each set bit can be kept or dropped independently, so there are 2^4 = 16 submasks.
  3. 3. What does x & -x compute for a positive integer x?

    Negation flips every bit above the lowest set bit and keeps the lowest set bit, so the AND isolates that single bit.
  4. 4. Why visit subsets in Gray order when keeping a running sum?

    Consecutive Gray codes differ in one bit, so a single addition or subtraction updates the sum. The loop still runs 2^n times.

Summary

  • Gray code orders the n-bit numbers so that neighbours (and the last and first) differ in one bit; the i-th code is i ^ (i >> 1).
  • Decode by XOR-ing all right shifts of the code; or build the list by reflecting and prefixing.
  • Counting masks from 0 to 2^n - 1 visits every subset; Gray order changes one element per step.
  • sub = (sub - 1) & mask enumerates all submasks, and doing it for every mask costs 3^n.
  • x & -x isolates the lowest set bit, x & (x - 1) clears it, and Gosper's hack steps through masks with a fixed popcount.

Next: Skip Lists, a randomized alternative to balanced trees.