What is a Gray Code? - It is a sequence of numbers from 0 to 2 ^ n — 1 (^ — exponentiation), in which every next number differs from the previous one in exactly one binary bit. For example, for n = 3. 000, 001, 011, 010, 110, 111, 101, 100

Notice: each transition changes only one bit. Such order is often used when you need to iterate over all subsets and quickly update the current state (for example, sum or product) when adding or removing one element.

How to construct a Gray Code? The simplest way is recursive construction (reflected Gray code):

For n = 1: 0, 1.

For larger n we will do it recursively.

n: take the sequence for n — 1, to the right of it write the same sequence but reversed, and for each number in the right part add a new most significant bit.

• In practice, the formula for direct computation of the i-th number in Gray code is more often used: g(i) = i ⊕ (i ≫ 1) where ⊕ is bitwise XOR, and >> is right shift. This works in O(1) and allows you to get the desired order without building a table.

• If you need to restore the original index i by the Gray code value g, then the inverse transformation is used:

int rev_gray(int g) {
    int i = 0;
    while (g) {
        i ^= g;
        g >>= 1;
    }
    return i;
}

One of the properties of Gray code: Take any permutation of numbers from 0 to 2 ^ n — 1 and calculate the sum of pairwise bitwise XOR between neighboring elements: S = (p0 ⊕ p1) + (p1 ⊕ p2) + ... + (p(2 ^ n − 2) ⊕ p(2 ^ n — 1)) (here ⊕ is bitwise XOR)

So, Gray code gives the minimum possible value of this sum among all permutations. Any other order of traversal will give a larger sum.

Also, Gray code has cyclicity, that is, if you connect the last and first elements, they will also differ in only 1 bit.

Where can this be useful?

• If you are solving a problem where you need to traverse all masks, and the cost of transition from one mask to another is exactly the XOR of their values (or monotonically depends on XOR), then Gray code gives the minimum total cost.

• This can be useful in problems where states are represented by bit strings, and the switching time between them is proportional to the number of changed bits, but with different weights (powers of two).