Код Грея: формула i ^ (i >> 1), обратное преобразование и LeetCode 89

Код Грея простыми словами: почему i ^ (i >> 1) меняет один бит, отражённое построение, обратное преобразование за O(log n), решение LeetCode 89 Gray Code и перебор подмножеств по одному элементу.

14 мин чтенияалгоритмы · битовые маски · python

Коротко

ЧтоКак
ОпределениеПоследовательность из 2n2^n чисел, соседние отличаются ровно одним битом
Прямая формулаg = i ^ (i >> 1) — O(1)O(1) на число
Обратная формулаb = g ^ (g >> 1) ^ (g >> 2) ^ ... — O(n)O(n) или O(log⁡n)O(\log n) сдвигов
Какой бит меняетсяНа шаге ii меняется бит номер «число нулей в конце ii» (i & -i)
LeetCode 89[i ^ (i >> 1) for i in range(1 << n)], O(2n)O(2^n) времени
Где пригодитсяПеребор подмножеств, где каждое следующее отличается одним элементом

Главная мысль: обычный двоичный счётчик при переходе 0111 → 1000 меняет четыре бита разом. Код Грея устроен так, что каждый шаг меняет ровно один бит — и при этом проходит все 2n2^n значений.

Зачем вообще такой код

Двоичный счёт неудобен там, где биты физически переключаются не одновременно. Классический пример — датчик угла поворота (энкодер): диск с дорожками, по одной на бит. Если при переходе с 7 на 8 один из четырёх контактов сработает чуть раньше остальных, датчик на мгновение покажет 15, 0 или что угодно ещё. С кодом Грея между соседними положениями меняется одна дорожка, и промежуточного мусора не бывает: прибор видит либо старое значение, либо новое.

Назван код в честь Фрэнка Грея из Bell Labs, который запатентовал его применение в 1950-х (идея известна и раньше — например, по головоломке «китайские кольца»). В программировании он всплывает реже, но на собеседованиях встречается регулярно: LeetCode 89 Gray Code, круговые перестановки битов, перебор подмножеств «с минимальными изменениями».

Как выглядит код Грея для n = 3

iдвоичныйкод Греязначение
00000000
10010011
20100113
30110102
41001106
51011117
61101015
71111004

Посмотрите на правый столбец кодов: каждая строка отличается от предыдущей одним битом. И последняя (100) отличается от первой (000) тоже одним битом — код циклический, его можно крутить по кругу.

Таких последовательностей для nn бит много. То, что в таблице, называется отражённым двоичным кодом Грея (reflected binary code). Когда говорят «код Грея» без уточнений, имеют в виду именно его.

Способ 1: отражённое построение

Это самый наглядный способ, и его легко придумать прямо на собеседовании.

Допустим, у нас есть код Грея для n−1n - 1 бит. Чтобы получить код для nn бит:

  1. Выписываем старый список и приписываем каждому числу слева 0.
  2. Выписываем старый список в обратном порядке и приписываем слева 1.
  3. Склеиваем.
n = 1:  0  1
n = 2:  00 01 | 11 10
n = 3:  000 001 011 010 | 110 111 101 100

Почему соседи по-прежнему отличаются одним битом:

  • внутри первой половины — потому что так было в старом списке, а приписанный 0 одинаковый;
  • внутри второй половины — то же самое, порядок обратный, но соседи те же;
  • на стыке половин стоят одинаковые хвосты (последний элемент старого списка и он же, развёрнутый первым), а отличается только старший бит.

Цикличность тоже сохраняется: первый элемент 0 + первый, последний 1 + первый — снова разница в одном бите.

На строках это выглядит так:

def reflected(n): codes = [''] for _ in range(n): codes = ['0' + c for c in codes] + ['1' + c for c in reversed(codes)] return codes print(reflected(3)) # ['000', '001', '011', '010', '110', '111', '101', '100']

Строки здесь только для наглядности. На числах «приписать 1 слева» — это выставить бит kk, а приписывать 0 вообще не нужно:

def gray_code_reflect(n): res = [0] for k in range(n): res += [x | (1 << k) for x in reversed(res)] return res print(gray_code_reflect(3)) # [0, 1, 3, 2, 6, 7, 5, 4]

Сложность: O(2n)O(2^n) времени — на каждом шаге список удваивается, суммарно 1+2+4+⋯+2n−1<2n1 + 2 + 4 + \dots + 2^{n-1} < 2^n операций. Память — сам ответ.

Способ 2: формула i ^ (i >> 1)

Тот же самый отражённый код получается одной строкой:

g(i)=i⊕⌊i2⌋g(i) = i \oplus \left\lfloor \frac{i}{2} \right\rfloor
def gray(i): return i ^ (i >> 1) print([gray(i) for i in range(8)]) # [0, 1, 3, 2, 6, 7, 5, 4]

По битам это значит: бит kk кода Грея равен XOR соседних битов kk и k+1k+1 исходного числа. Старший бит переходит без изменений (у него «сосед сверху» — ноль).

i      = 1 0 1 1   (11)
i >> 1 = 0 1 0 1
XOR    = 1 1 1 0   (14)

Почему меняется ровно один бит

Посмотрим, что происходит при переходе от i−1i - 1 к ii. Пусть ii заканчивается на 1 и tt нулей:

i - 1 = ...x 0 1 1 1     (t единиц в конце)
i     = ...x 1 0 0 0     (t нулей в конце)

В двоичной записи поменялись младшие t+1t + 1 бит (позиции 0..t0..t), всё выше — без изменений.

Бит kk кода Грея — это bk⊕bk+1b_k \oplus b_{k+1}:

  • для k<tk < t оба бита bkb_k и bk+1b_{k+1} перевернулись, XOR не изменился;
  • для k=tk = t перевернулся только btb_t, а bt+1b_{t+1} остался прежним — этот бит Грея меняется;
  • для k>tk > t ничего не менялось.

Итого меняется ровно один бит, и его номер tt — количество нулей в конце ii. Это полезный факт сам по себе:

for i in range(1, 1 << 12): assert gray(i) ^ gray(i - 1) == i & -i # i & -i — младший единичный бит i

Почему это тот же отражённый код

Отражённое построение говорит: вторая половина списка — это первая, развёрнутая и со старшим битом. То есть элемент с номером 2n−1−i2^n - 1 - i должен равняться g(i)g(i) с перевёрнутым битом n−1n - 1.

Число 2n−1−i2^n - 1 - i — это ii с инвертированными всеми nn битами. Если инвертировать все биты ii, то в соседних парах bk⊕bk+1b_k \oplus b_{k+1} (при k<n−1k < n-1) перевернутся оба бита и XOR не изменится. Поменяется только старший бит кода — он ни с кем не «спарен». Ровно то, что требует отражение. Различаются эти два способа только тем, что формула позволяет получить ii-й код сразу, без построения всего списка.

Обратное преобразование: из кода Грея в число

Иногда дан код Грея, а нужно узнать его номер в последовательности. Раз gk=bk⊕bk+1g_k = b_k \oplus b_{k+1}, то двигаясь сверху вниз:

bn−1=gn−1,bk=gk⊕bk+1b_{n-1} = g_{n-1}, \quad b_k = g_k \oplus b_{k+1}

Раскрываем рекурсию: bkb_k — это XOR всех битов кода от kk и выше. На битовых операциях это XOR всех сдвигов:

b=g⊕(g≫1)⊕(g≫2)⊕…b = g \oplus (g \gg 1) \oplus (g \gg 2) \oplus \dots
def from_gray(g): b = 0 while g: b ^= g g >>= 1 return b print(from_gray(6)) # 4: в таблице код 110 стоит на позиции 4

Это O(n)O(n) итераций, где nn — число бит. Для фиксированной ширины есть трюк за O(log⁡n)O(\log n): XOR-префикс можно собирать удвоением, как префиксные суммы. После g ^= g >> 1 каждый бит хранит XOR двух битов, после g ^= g >> 2 — четырёх, и так далее.

def from_gray32(g): # для чисел до 32 бит g ^= g >> 16 g ^= g >> 8 g ^= g >> 4 g ^= g >> 2 g ^= g >> 1 return g for i in range(1 << 16): assert from_gray32(gray(i)) == i

Порядок сдвигов не важен: XOR коммутативен, и в итоге каждый бит собирает XOR всех битов выше себя. Обычно идут от больших сдвигов к малым — так привычнее.

Обратное преобразование — та же идея, что в задаче «найти число без пары»: XOR сам себе обратен (a⊕a=0a \oplus a = 0), поэтому из цепочки XOR можно «вытащить» исходные биты. Подробнее про свойства XOR — в статье про битовые операции.

LeetCode 89. Gray Code

Условие. Дано nn (1≤n≤161 \le n \le 16). Верните любую последовательность из 2n2^n чисел, такую что:

  • каждое число в диапазоне [0,2n−1][0, 2^n - 1];
  • первое число — 0;
  • каждое число встречается ровно один раз;
  • соседние числа отличаются ровно одним битом, первое и последнее — тоже.

Пример: n = 2 → [0, 1, 3, 2] (подходит и [0, 2, 3, 1]).

Наивный подход: бэктрекинг

Если формулу не помнишь, задачу можно решить перебором: начинаем с 0, пробуем перевернуть каждый бит, идём в непосещённое число, при тупике откатываемся.

def gray_code_backtrack(n): seen = {0} path = [0] def dfs(): if len(path) == 1 << n: return True last = path[-1] for k in range(n): nxt = last ^ (1 << k) if nxt not in seen: seen.add(nxt) path.append(nxt) if dfs(): return True seen.remove(nxt) path.pop() return False dfs() return path print(gray_code_backtrack(3)) # [0, 1, 3, 2, 6, 7, 5, 4]

Здесь тупиков не бывает: если всегда переворачивать самый младший бит, который ведёт в новое число, жадный обход сразу даёт отражённый код Грея. Но доказывать это на собеседовании долго, а рекурсия глубиной 216=655362^{16} = 65536 в Python упадёт с RecursionError без sys.setrecursionlimit. Как разговорный шаг «вот как бы я подошёл в лоб» — нормально, как финальный ответ — нет. Про общую схему таких переборов — в статье про бэктрекинг.

Оптимальное решение

class Solution: def grayCode(self, n: int) -> list[int]: return [i ^ (i >> 1) for i in range(1 << n)]

То же на JavaScript:

const grayCode = (n) => Array.from({ length: 1 << n }, (_, i) => i ^ (i >> 1)) console.log(grayCode(3)) // [0, 1, 3, 2, 6, 7, 5, 4]

Сложность: O(2n)O(2^n) времени и O(1)O(1) дополнительной памяти, не считая ответа. Лучше нельзя — ответ сам по себе длины 2n2^n.

Условие «первое и последнее отличаются одним битом» выполнено автоматически: последний элемент g(2n−1)=2n−1g(2^n - 1) = 2^{n-1}, у него единственная единица в старшем бите.

Как проверить ответ

Полезно уметь написать проверку — и для себя, и если интервьюер спросит «как вы убедитесь, что это верно»:

def is_valid_gray(seq, n): if len(seq) != 1 << n or len(set(seq)) != len(seq) or seq[0] != 0: return False for a, b in zip(seq, seq[1:] + seq[:1]): # с замыканием в кольцо if bin(a ^ b).count('1') != 1: return False return True assert all(is_valid_gray(Solution().grayCode(n), n) for n in range(1, 17))

a ^ b оставляет единицы ровно там, где числа различаются, — дальше достаточно посчитать единицы.

Родственные задачи

LeetCode 1238. Circular Permutation in Binary Representation

То же самое, но последовательность должна начинаться не с 0, а с заданного start. Решение — сдвинуть весь код Грея XOR-ом:

def circular_permutation(n, start): return [start ^ i ^ (i >> 1) for i in range(1 << n)] print(circular_permutation(2, 3)) # [3, 2, 0, 1]

XOR с константой — биекция на [0,2n)[0, 2^n) и не меняет разницу между соседями: (s⊕a)⊕(s⊕b)=a⊕b(s \oplus a) \oplus (s \oplus b) = a \oplus b. Поэтому все свойства сохраняются, а первым элементом становится s⊕0=ss \oplus 0 = s.

LeetCode 1611. Minimum One Bit Operations to Make Integers Zero

Hard-задача с хитро сформулированными операциями над битами. Если разобраться, разрешённые операции — это ровно переходы между соседями в коде Грея, а ответ — номер числа nn в этой последовательности. То есть решение — обратное преобразование:

def minimum_one_bit_operations(n): return from_gray(n) print(minimum_one_bit_operations(3), minimum_one_bit_operations(6)) # 2 4

Догадаться до этого на собеседовании трудно, но если код Грея уже знаком — задача решается в три строки.

Применение: перебор подмножеств по одному элементу

Стандартный перебор подмножеств битовыми масками (for mask in range(1 << n)) на каждом шаге может поменять много элементов разом — как в 0111 → 1000. Если для каждого подмножества нужно что-то пересчитывать (сумму, произведение, состояние структуры данных), это O(n)O(n) на маску и O(n⋅2n)O(n \cdot 2^n) всего. Про обычный перебор и бэктрекинг подробно — в разборе задачи Subsets.

В порядке кода Грея соседние подмножества отличаются ровно одним элементом: его либо добавили, либо убрали. Значит, состояние можно обновлять за O(1)O(1) на шаг. Какой элемент поменялся — уже знаем: номер младшего единичного бита ii.

def subset_sums(nums): n = len(nums) total = 0 sums = [0] # пустое подмножество for i in range(1, 1 << n): bit = (i & -i).bit_length() - 1 # какой элемент меняется if gray(i) >> bit & 1: # бит включился — элемент добавили total += nums[bit] else: # выключился — убрали total -= nums[bit] sums.append(total) return sums print(subset_sums([3, 5, 7])) # [0, 3, 8, 5, 12, 15, 10, 7]

Порядок подмножеств для ['a', 'b', 'c'] получается такой:

[] → [a] → [a, b] → [b] → [b, c] → [a, b, c] → [a, c] → [c]

Где это реально нужно:

  • Подсчёт сумм всех подмножеств в meet-in-the-middle: 2n/22^{n/2} сумм для каждой половины за O(1)O(1) на сумму вместо O(n)O(n).
  • Перебор с дорогим состоянием: подмножество рёбер графа в DSU с откатом, подмножество строк матрицы, где добавление и удаление стоят дёшево, а пересчёт с нуля — дорого. Изменение одного элемента за шаг — минимум, который вообще возможен.
  • Формула включений-исключений: знак слагаемого зависит от чётности размера подмножества, а размер на каждом шаге меняется на ±1 — его тоже не нужно пересчитывать.
  • Тестирование комбинаций флагов (в железе и в софте): если каждый шаг переключает один флаг, при падении сразу понятно, какой переключатель виноват.

Тот же самый счётчик «номер младшего единичного бита ii» говорит, какой диск двигать на шаге ii в Ханойских башнях. Это не совпадение: оптимальное решение Ханойской башни и отражённый код Грея имеют одну и ту же рекурсивную структуру «половина, переход старшего элемента, половина задом наперёд». А если перебирать маски без требования одного изменения, но с подмасками, — это уже техника из ДП по подмножествам.

Где ещё встречается код Грея

  • Энкодеры положения и угла — исходное применение: механические и оптические датчики.
  • Карты Карно — оси подписаны в порядке кода Грея (00, 01, 11, 10), чтобы соседние клетки отличались одной переменной, и склейки были видны глазами.
  • Передача между тактовыми доменами — указатели асинхронных FIFO-буферов в цифровых схемах передают в коде Грея: если синхронизатор «поймает» значение в момент переключения, ошибка будет максимум на единицу, а не в произвольную сторону.
  • Генетические алгоритмы — кодирование числовых параметров кодом Грея делает мутацию одного бита «маленьким» шагом по значению чаще, чем при двоичной записи.

Типичные ошибки

Путают направление формулы. i ^ (i >> 1) — из номера в код. Обратно нужно XOR всех сдвигов, а не g ^ (g << 1) и не ещё раз g ^ (g >> 1). Проверка на одном числе: from_gray(gray(5)) == 5.

Сдвиг не в ту сторону. i ^ (i << 1) даёт числа, которые выходят за [0,2n)[0, 2^n), и ничего общего с кодом Грея не имеет.

Забывают про замыкание. В LeetCode 89 первое и последнее числа тоже должны отличаться одним битом. Отражённый код это гарантирует, а самописный перебор — не всегда. При проверке сравнивайте пары по кругу.

Знаковые сдвиги в JavaScript. Побитовые операции в JS работают с 32-битными знаковыми числами. Для LeetCode 89 (n≤16n \le 16) это не проблема, но обратное преобразование для числа со старшим 31-м битом вернёт отрицательный результат. Используйте >>> для сдвига и >>> 0 для результата:

function fromGray(g) { let b = 0 while (g) { b ^= g g >>>= 1 } return b >>> 0 } console.log(fromGray(0b110)) // 4

Строят код строками. Решение со строками '0' + c проходит, но в nn раз медленнее и съедает память на 2n2^n строк. На собеседовании покажите его как объяснение, а сдайте формулу.

Что спрашивают на собеседовании

  1. Сгенерируйте код Грея для nn бит (LeetCode 89). Ожидают формулу или отражённое построение и объяснение, почему соседи отличаются одним битом.
  2. Докажите, что i ^ (i >> 1) работает. Аргумент с «единицами в конце» из раздела выше — короткий и убедительный.
  3. Как по коду Грея найти номер? Обратное преобразование через XOR сдвигов.
  4. Начать с произвольного числа (LeetCode 1238) — XOR с start.
  5. Переберите подмножества так, чтобы каждое следующее отличалось одним элементом. Код Грея плюс i & -i для номера элемента.

Если запомнить одну вещь — запомните формулу и доказательство через перенос в младших битах. Всё остальное из них выводится за пару минут у доски.

Потренироваться в спокойной обстановке

Все задачи