Что такое код Грея? Это последовательность чисел от 0 до 2 ^ n — 1 (^ — возведение в степень), в которой каждое следующее число отличается от предыдущего ровно в одном двоичном разряде (одном бите). Например, для n = 3. 000, 001, 011, 010, 110, 111, 101, 100

• Обратите внимание: каждый переход меняет только один бит. Такой порядок часто используют, когда нужно перебрать все подмножества и при этом быстро обновлять текущее состояние (например, сумму или произведение) при добавлении/удалении одного элемента.

Как построить код Грея? Самый простой способ – рекурсивное построение (отражённый код Грея):

• Для n = 1 n = 1: 0, 1.

Для n больших будем делать рекурсивно. 1. n: берём последовательность для n — 1, справо от от неё записываем такую последовательность но развёрнутую и при этом для каждого числа в правой части добовляем новый старший бит. На практике же чаще используют формулу для прямого вычисления i-го числа в коде Грея: g(i) = i ⊕ (i ≫ 1) где ⊕ – побитовое исключающее ИЛИ, а >> – сдвиг вправо. Это работает за O(1) и позволяет получить нужный порядок без построения таблицы.

Если же нужно восстановить исходный номер i по значению кода Грея g, то используется обратное преобразование:

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

• Одно из свойст Кода Грея: Возьмём любую перестановку чисел от 0 до 2 ^ n — 1 и посчитаем сумму попарных побитовых XOR между соседними элементами: S = (p0 ⊕ p1) + (p1 ⊕ p2) + ... + (p(2 ^ n − 2) ⊕ p(2 ^ n — 1)) (здесь ⊕ – побитовое XOR)
• Так вот, код Грея даёт минимально возможное значение этой суммы среди всех перестановок. Любой другой порядок обхода даст сумму больше.

• Так же код грея обладает цикличностью то есть если соеденить последний и первый элемент, они тоже будут отличатся только в 1 бите.

Где это может пригодиться?

• Если вы решаете задачу, где нужно обойти все маски, а стоимость перехода из одной маски в другую равна именно XOR их значений (или монотонно зависит от XOR), то код Грея даст минимальную суммарную стоимость.

• Это может быть полезно в задачах, где состояния представляются битовыми строками, а время переключения между ними пропорционально числу изменяемых битов, но с разными весами (степенями двойки).