Коды Грея

Задача

Frank Gray (13 September 1887 – 23 May 1969) was a physicist and researcher at Bell Labs who made numerous innovations in television, both mechanical and electronic

Frank Gray (13 September 1887 – 23 May 1969) was a physicist and researcher at Bell Labs who made numerous innovations in television, both mechanical and electronic

Коды Грея получили своё название по имени Франка Грея (Frank Gray), физика из Bell Telephone Laboratories, который в 1930-х годах изобрёл метод, в настоящее время используемый для передачи цветного телевизионного сигнала, совместно с существующими методами передачи и получения чёрно-белого сигнала; т.е. при получении цветного сигнала чёрно-белым приёмником изображение выводится оттенками серого цвета.
Хотя существует множество различных вариантов кодов Грея, рассмотрим только один: «двоичный отражённый (рефлексный) код Грея». Именно этот код обычно имеется в виду, когда говорят о неконкретном «коде Грея».
Отображённый двоичный код Грея строится следующим образом. Начинаем со строк [latex]0[/latex] и [latex]1[/latex], которые представляют соответственно целые числа [latex]0[/latex] и [latex]1[/latex].
[latex]0[/latex]
[latex]1[/latex]
Возьмём отражение этих строк относительно горизонтальной оси после приведённого списка и поместим [latex]1[/latex] слева от новых записей списка, а слева от уже имевшихся разместим [latex]0[/latex].
[latex]00[/latex]
[latex]01[/latex]
[latex]11[/latex]
[latex]10[/latex]
Таким образом получен отражённый код Грея для [latex]n = 2[/latex]. Чтобы получить код для [latex]n = 3[/latex], повторим описанную процедуру и получим:
[latex]000[/latex]
[latex]001[/latex]
[latex]011[/latex]
[latex]010[/latex]
[latex]110[/latex]
[latex]111[/latex]
[latex]101[/latex]
[latex]100[/latex]
При таком способе построения легко увидеть по индукции по [latex]n[/latex], что, во-первых, каждая из [latex]2n[/latex] комбинаций битов появляется в списке, причём только один раз; во-вторых, при переходе от одного элемента списка к рядом стоящему изменяется только один бит; в-третьих, только один бит изменяется при переходе от последнего элемента списка к первому. Коды Грея, обладающие последним свойством называются циклическими, и отражённый код Грея обязательно является таковым.
Для каждого заданного числа [latex]k[/latex] вывести десятичное значение [latex]k[/latex]-го кода Грея.

Входные данные

Во входном файле содержится некоторый набор тестовых данных, каждое число [latex]k[/latex] ([latex]0 ≤ k ≤ 10^{18}[/latex]) в наборе задано в отдельной строке. Количество наборов данных в одном тесте не превышает [latex]10^5[/latex].

Выходные данные

Для каждого заданного числа [latex]k[/latex] вывести в отдельной строке десятичное значение [latex]k[/latex]-го кода Грея.

Тесты

Входные данные Выходные данные
1 3 2
14 9
5 7
12 10
2 0 0
72 108
265 397
4781 7163
50642 42811
3 1010234 581415
96721758 119682801
640214927 893162568
2456987013 3679188807
51027963402 60418988303
1000000000000000000 797398725282889728

Код программы

Решение задачи

Объявляем переменную [latex]k[/latex] ([latex]0 ≤ k ≤ 10^{18}[/latex]) типа unsigned long int для считывания чисел из входного потока. Цикл while работает столько раз, сколько чисел во входном потоке (по условию задачи их количество [latex]\le 10^5[/latex]). В цикле вычисляется Код Грея числа [latex]k[/latex] путем побитовой операции «исключающее ИЛИ», применимого к [latex]k[/latex] и к результату побитового сдвига [latex]k[/latex] на [latex]1[/latex] бит вправо ([latex]k \gg 1[/latex]).
Ссылка на алгоритм ниже.

Ссылки

Code Gray: theory
e-olymp
ideone

e-olymp 1519. Коды Грея

Задача

Френк Грей. Bell Lab 1930

Френк Грей. Bell Lab 1930

Бинарные коды Грея генерируются следующим образом. Рассмотрим последовательность
0
1
Отобразим строки вниз относительно горизонтальной черты, припишем к первой половине строк спереди 0, а ко второй отображенной половине 1. Получим последовательность:
00
01
11
10
Продолжая процесс, на следующем шаге получим последовательность из 8 чисел. Справа от кода находится его десятичное значение
000 0
001 1
011 3
010 2
110 6
111 7
101 5
100 4
Приведенные последовательности называются кодами Грея длины $n = 1, 2, 3$. Всего существует $2n$ разных кодов длины $n$. Каждые два соседних кода отличаются одним битом.

Входные данные

Первая строка содержит количество тестов $n$ (не более 250000). Каждая следующая строка содержит два числа: $n$ $(1 ≤ n ≤ 30)$ и $k$ $(0 ≤ k < 2^n)$.

Выходные данные

Для каждого теста в отдельной строке вывести число, которое находится в $k$ — ой позиции последовательности кодов Грея длины $n$.

Тесты

Входные данные Выходные данные
1 14
1 0
1 1
2 0
2 1
2 2
2 3
3 0
3 1
3 2
3 3
3 4
3 5
3 6
3 7
0
1
0
1
3
2
0
1
3
2
6
7
5
4
2 3
2 1
1 2
3 3
1
1
2
3 1
0 0
0
4 2
2 3
1 3
2
1

Код программы

Решение

В случае, если значение бинарного кода находится в первой части последовательности, т.е. $x$ < $2^{n-1}$, то ищем число, стоящее в позиции $k$ кода Грея длины $n-1$. В другом же случае ищем число, прибавив к
$2^{n-1}$ число в позиции $2^n-k-1$ длины $n-1$. Оформим данный алгоритм в виде рекурсивной функции.

e-olymp

ideone