e-olymp
Задачи

Коды Грея

Коды Грея

Коды Грея получили своё название по имени Франка Грея (Frank Gray), физика из Bell Telephone Laboratories, который в 1930-х годах изобрёл метод, в настоящее время используемый для передачи цветного телевизионного сигнала, совместно с существующими методами передачи и получения чёрно-белого сигнала; т.е. при получении цветного сигнала чёрно-белым приёмником изображение выводится оттенками серого цвета.

Хотя существует множество различных вариантов кодов Грея, рассмотрим только один: "двоичный отражённый (рефлексный) код Грея". Именно этот код обычно имеется в виду, когда говорят о неконкретном "коде Грея".

Отображённый двоичный код Грея строится следующим образом. Начинаем со строк 0 и 1, которые представляют соответственно целые числа 0 и 1.

0
1

Возьмём отражение этих строк относительно горизонтальной оси после приведённого списка и поместим 1 слева от новых записей списка, а слева от уже имевшихся разместим 0.

00
01
11
10

Таким образом получен отражённый код Грея для n = 2. Чтобы получить код для n = 3, повторим описанную процедуру и получим:

000
001
011
010
110
111
101
100

При таком способе построения легко увидеть по индукции по n, что, во-первых, каждая из 2n комбинаций битов появляется в списке, причём только один раз; во-вторых, при переходе от одного элемента списка к рядом стоящему изменяется только один бит; в-третьих, только один бит изменяется при переходе от последнего элемента списка к первому. Коды Грея, обладающие последним свойством называются циклическими, и отражённый код Грея обязательно является таковым.

Для каждого заданного числа k вывести десятичное значение k-го кода Грея.

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

Во входном файле содержится некоторый набор тестовых данных, каждое число k (0k1018) в наборе задано в отдельной строке. Количество наборов данных в одном тесте не превышает 105.

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

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

Лимит времени 1 секунда
Лимит использования памяти 64 MiB
Входные данные
3
14
5
12
Выходные данные
2
9
7
10