Код Грея

Код Грея — такая перестановка чисел от $0$ до $2^k - 1$, что соседние элементы отличаются ровно одним битом. Строится он неожиданно коротко:

$$g(n) = n \oplus (n \gg 1).$$

При $k = 3$ получается $000, 001, 011, 010, 110, 111, 101, 100$.

Почему работает

Соседние $n$ и $n+1$ отличаются хвостом вида $0\underbrace{1\ldots1}_{t} \to 1\underbrace{0\ldots0}_{t}$. После XOR со сдвигом от этого хвоста остаётся ровно один изменившийся бит — тот, что был на границе.

Другой взгляд, рекурсивный: код Грея для $k$ битов — это код для $k-1$ бита, потом он же в обратном порядке с добавленной единицей слева. Отсюда видно и то, что все значения различны, и то, что соседи отличаются одним битом, включая границу половин.

Обратное преобразование

unsigned long long inverse(unsigned long long g) {
    unsigned long long n = 0;
    for (; g; g >>= 1) n ^= g;
    return n;
}

Из $g = n \oplus (n \gg 1)$ следует $n = g \oplus (n \gg 1)$; раскрывая рекурсию, получаем $n = g \oplus (g \gg 1) \oplus (g \gg 2) \oplus \ldots$ — это и есть цикл.

Где применяется

Обход всех подмножеств с минимальными изменениями. Если пересчёт при добавлении или удалении одного элемента дешевле, чем счёт с нуля, порядок Грея экономит время.

Ханойские башни. Номер диска, который двигают на $i$-м шаге, равен номеру бита, изменившегося между $g(i-1)$ и $g(i)$.

Физические датчики. На механическом энкодере при переходе между соседними положениями меняется один контакт — значит, промежуточных ложных значений не бывает.

Смежное

• Исключающее «или»;
• Маска как множество.