Код Грея: формула i ^ (i >> 1), обратное преобразование и LeetCode 89
Код Грея простыми словами: почему i ^ (i >> 1) меняет один бит, отражённое построение, обратное преобразование за O(log n), решение LeetCode 89 Gray Code и перебор подмножеств по одному элементу.
Коротко
| Что | Как |
|---|---|
| Определение | Последовательность из чисел, соседние отличаются ровно одним битом |
| Прямая формула | g = i ^ (i >> 1) — на число |
| Обратная формула | b = g ^ (g >> 1) ^ (g >> 2) ^ ... — или сдвигов |
| Какой бит меняется | На шаге меняется бит номер «число нулей в конце » (i & -i) |
| LeetCode 89 | [i ^ (i >> 1) for i in range(1 << n)], времени |
| Где пригодится | Перебор подмножеств, где каждое следующее отличается одним элементом |
Главная мысль: обычный двоичный счётчик при переходе 0111 → 1000 меняет четыре бита разом. Код Грея устроен так, что каждый шаг меняет ровно один бит — и при этом проходит все значений.
Зачем вообще такой код
Двоичный счёт неудобен там, где биты физически переключаются не одновременно. Классический пример — датчик угла поворота (энкодер): диск с дорожками, по одной на бит. Если при переходе с 7 на 8 один из четырёх контактов сработает чуть раньше остальных, датчик на мгновение покажет 15, 0 или что угодно ещё. С кодом Грея между соседними положениями меняется одна дорожка, и промежуточного мусора не бывает: прибор видит либо старое значение, либо новое.
Назван код в честь Фрэнка Грея из Bell Labs, который запатентовал его применение в 1950-х (идея известна и раньше — например, по головоломке «китайские кольца»). В программировании он всплывает реже, но на собеседованиях встречается регулярно: LeetCode 89 Gray Code, круговые перестановки битов, перебор подмножеств «с минимальными изменениями».
Как выглядит код Грея для n = 3
| i | двоичный | код Грея | значение |
|---|---|---|---|
| 0 | 000 | 000 | 0 |
| 1 | 001 | 001 | 1 |
| 2 | 010 | 011 | 3 |
| 3 | 011 | 010 | 2 |
| 4 | 100 | 110 | 6 |
| 5 | 101 | 111 | 7 |
| 6 | 110 | 101 | 5 |
| 7 | 111 | 100 | 4 |
Посмотрите на правый столбец кодов: каждая строка отличается от предыдущей одним битом. И последняя (100) отличается от первой (000) тоже одним битом — код циклический, его можно крутить по кругу.
Таких последовательностей для бит много. То, что в таблице, называется отражённым двоичным кодом Грея (reflected binary code). Когда говорят «код Грея» без уточнений, имеют в виду именно его.
Способ 1: отражённое построение
Это самый наглядный способ, и его легко придумать прямо на собеседовании.
Допустим, у нас есть код Грея для бит. Чтобы получить код для бит:
- Выписываем старый список и приписываем каждому числу слева
0. - Выписываем старый список в обратном порядке и приписываем слева
1. - Склеиваем.
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 слева» — это выставить бит , а приписывать 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]
Сложность: времени — на каждом шаге список удваивается, суммарно операций. Память — сам ответ.
Способ 2: формула i ^ (i >> 1)
Тот же самый отражённый код получается одной строкой:
def gray(i): return i ^ (i >> 1) print([gray(i) for i in range(8)]) # [0, 1, 3, 2, 6, 7, 5, 4]
По битам это значит: бит кода Грея равен XOR соседних битов и исходного числа. Старший бит переходит без изменений (у него «сосед сверху» — ноль).
i = 1 0 1 1 (11)
i >> 1 = 0 1 0 1
XOR = 1 1 1 0 (14)
Почему меняется ровно один бит
Посмотрим, что происходит при переходе от к . Пусть заканчивается на 1 и нулей:
i - 1 = ...x 0 1 1 1 (t единиц в конце)
i = ...x 1 0 0 0 (t нулей в конце)
В двоичной записи поменялись младшие бит (позиции ), всё выше — без изменений.
Бит кода Грея — это :
- для оба бита и перевернулись, XOR не изменился;
- для перевернулся только , а остался прежним — этот бит Грея меняется;
- для ничего не менялось.
Итого меняется ровно один бит, и его номер — количество нулей в конце . Это полезный факт сам по себе:
for i in range(1, 1 << 12): assert gray(i) ^ gray(i - 1) == i & -i # i & -i — младший единичный бит i
Почему это тот же отражённый код
Отражённое построение говорит: вторая половина списка — это первая, развёрнутая и со старшим битом. То есть элемент с номером должен равняться с перевёрнутым битом .
Число — это с инвертированными всеми битами. Если инвертировать все биты , то в соседних парах (при ) перевернутся оба бита и XOR не изменится. Поменяется только старший бит кода — он ни с кем не «спарен». Ровно то, что требует отражение. Различаются эти два способа только тем, что формула позволяет получить -й код сразу, без построения всего списка.
Обратное преобразование: из кода Грея в число
Иногда дан код Грея, а нужно узнать его номер в последовательности. Раз , то двигаясь сверху вниз:
Раскрываем рекурсию: — это XOR всех битов кода от и выше. На битовых операциях это XOR всех сдвигов:
def from_gray(g): b = 0 while g: b ^= g g >>= 1 return b print(from_gray(6)) # 4: в таблице код 110 стоит на позиции 4
Это итераций, где — число бит. Для фиксированной ширины есть трюк за : 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 сам себе обратен (), поэтому из цепочки XOR можно «вытащить» исходные биты. Подробнее про свойства XOR — в статье про битовые операции.
LeetCode 89. Gray Code
Условие. Дано (). Верните любую последовательность из чисел, такую что:
- каждое число в диапазоне ;
- первое число — 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]
Здесь тупиков не бывает: если всегда переворачивать самый младший бит, который ведёт в новое число, жадный обход сразу даёт отражённый код Грея. Но доказывать это на собеседовании долго, а рекурсия глубиной в 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]
Сложность: времени и дополнительной памяти, не считая ответа. Лучше нельзя — ответ сам по себе длины .
Условие «первое и последнее отличаются одним битом» выполнено автоматически: последний элемент , у него единственная единица в старшем бите.
Как проверить ответ
Полезно уметь написать проверку — и для себя, и если интервьюер спросит «как вы убедитесь, что это верно»:
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 с константой — биекция на и не меняет разницу между соседями: . Поэтому все свойства сохраняются, а первым элементом становится .
LeetCode 1611. Minimum One Bit Operations to Make Integers Zero
Hard-задача с хитро сформулированными операциями над битами. Если разобраться, разрешённые операции — это ровно переходы между соседями в коде Грея, а ответ — номер числа в этой последовательности. То есть решение — обратное преобразование:
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. Если для каждого подмножества нужно что-то пересчитывать (сумму, произведение, состояние структуры данных), это на маску и всего. Про обычный перебор и бэктрекинг подробно — в разборе задачи Subsets.
В порядке кода Грея соседние подмножества отличаются ровно одним элементом: его либо добавили, либо убрали. Значит, состояние можно обновлять за на шаг. Какой элемент поменялся — уже знаем: номер младшего единичного бита .
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: сумм для каждой половины за на сумму вместо .
- Перебор с дорогим состоянием: подмножество рёбер графа в DSU с откатом, подмножество строк матрицы, где добавление и удаление стоят дёшево, а пересчёт с нуля — дорого. Изменение одного элемента за шаг — минимум, который вообще возможен.
- Формула включений-исключений: знак слагаемого зависит от чётности размера подмножества, а размер на каждом шаге меняется на ±1 — его тоже не нужно пересчитывать.
- Тестирование комбинаций флагов (в железе и в софте): если каждый шаг переключает один флаг, при падении сразу понятно, какой переключатель виноват.
Тот же самый счётчик «номер младшего единичного бита » говорит, какой диск двигать на шаге в Ханойских башнях. Это не совпадение: оптимальное решение Ханойской башни и отражённый код Грея имеют одну и ту же рекурсивную структуру «половина, переход старшего элемента, половина задом наперёд». А если перебирать маски без требования одного изменения, но с подмасками, — это уже техника из ДП по подмножествам.
Где ещё встречается код Грея
- Энкодеры положения и угла — исходное применение: механические и оптические датчики.
- Карты Карно — оси подписаны в порядке кода Грея (
00, 01, 11, 10), чтобы соседние клетки отличались одной переменной, и склейки были видны глазами. - Передача между тактовыми доменами — указатели асинхронных FIFO-буферов в цифровых схемах передают в коде Грея: если синхронизатор «поймает» значение в момент переключения, ошибка будет максимум на единицу, а не в произвольную сторону.
- Генетические алгоритмы — кодирование числовых параметров кодом Грея делает мутацию одного бита «маленьким» шагом по значению чаще, чем при двоичной записи.
Типичные ошибки
Путают направление формулы. i ^ (i >> 1) — из номера в код. Обратно нужно XOR всех сдвигов, а не g ^ (g << 1) и не ещё раз g ^ (g >> 1). Проверка на одном числе: from_gray(gray(5)) == 5.
Сдвиг не в ту сторону. i ^ (i << 1) даёт числа, которые выходят за , и ничего общего с кодом Грея не имеет.
Забывают про замыкание. В LeetCode 89 первое и последнее числа тоже должны отличаться одним битом. Отражённый код это гарантирует, а самописный перебор — не всегда. При проверке сравнивайте пары по кругу.
Знаковые сдвиги в JavaScript. Побитовые операции в JS работают с 32-битными знаковыми числами. Для LeetCode 89 () это не проблема, но обратное преобразование для числа со старшим 31-м битом вернёт отрицательный результат. Используйте >>> для сдвига и >>> 0 для результата:
function fromGray(g) { let b = 0 while (g) { b ^= g g >>>= 1 } return b >>> 0 } console.log(fromGray(0b110)) // 4
Строят код строками. Решение со строками '0' + c проходит, но в раз медленнее и съедает память на строк. На собеседовании покажите его как объяснение, а сдайте формулу.
Что спрашивают на собеседовании
- Сгенерируйте код Грея для бит (LeetCode 89). Ожидают формулу или отражённое построение и объяснение, почему соседи отличаются одним битом.
- Докажите, что
i ^ (i >> 1)работает. Аргумент с «единицами в конце» из раздела выше — короткий и убедительный. - Как по коду Грея найти номер? Обратное преобразование через XOR сдвигов.
- Начать с произвольного числа (LeetCode 1238) — XOR с
start. - Переберите подмножества так, чтобы каждое следующее отличалось одним элементом. Код Грея плюс
i & -iдля номера элемента.
Если запомнить одну вещь — запомните формулу и доказательство через перенос в младших битах. Всё остальное из них выводится за пару минут у доски.