Задача
Коды Грея получили своё название по имени Франка Грея (Frank Gray), физика из Bell Telephone Laboratories, который в 1930-х годах изобрёл метод, в настоящее время используемый для передачи цветного телевизионного сигнала, совместно с существующими методами передачи и получения чёрно-белого сигнала; т.е. при получении цветного сигнала чёрно-белым приёмником изображение выводится оттенками серого цвета.
Хотя существует множество различных вариантов кодов Грея, рассмотрим только один: «двоичный отражённый (рефлексный) код Грея». Именно этот код обычно имеется в виду, когда говорят о неконкретном «коде Грея».
Отображённый двоичный код Грея строится следующим образом. Начинаем со строк [latex]0[/latex] и [latex]1[/latex], которые представляют соответственно целые числа [latex]0[/latex] и [latex]1[/latex].
| 0 |
|---|
| 1 |
Возьмём отражение этих строк относительно горизонтальной оси после приведённого списка и поместим [latex]1[/latex] слева от новых записей списка, а слева от уже имевшихся разместим [latex]0[/latex].
| 00 |
|---|
| 01 |
| 11 |
| 10 |
Таким образом получен отражённый код Грея для [latex]n = 2[/latex]. Чтобы получить код для [latex]n = 3[/latex], повторим описанную процедуру и получим:
| 000 |
|---|
| 001 |
| 011 |
| 010 |
| 110 |
| 111 |
| 101 |
| 100 |
При таком способе построения легко увидеть по индукции по [latex]n[/latex], что, во-первых, каждая из [latex]2^n[/latex] комбинаций битов появляется в списке, причём только один раз; во-вторых, при переходе от одного элемента списка к рядом стоящему изменяется только один бит; в-третьих, только один бит изменяется при переходе от последнего элемента списка к первому. Коды Грея, обладающие последним свойством называются циклическими, и отражённый код Грея обязательно является таковым.
Для каждого заданного числа [latex]k[/latex] вывести десятичное значение [latex]k[/latex]-го кода Грея.
Входные данные
Во входном файле содержится некоторый набор тестовых данных, каждое число [latex]k (0 < k < 10^{18})[/latex] в наборе задано в отдельной строке. Количество наборов данных в одном тесте не превышает [latex]10^5[/latex].
Выходные данные
Для каждого заданного числа [latex]k[/latex] вывести в отдельной строке десятичное значение [latex]k[/latex]-го кода Грея.
| № | Входные данные | Выходные данные |
|---|---|---|
| 1 | 3 14 5 12 |
2 9 7 10 |
| 2 | 10 50 |
15 43 |
Код программы
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
import java.util.*; import java.lang.*; import java.io.*; class Main { static BufferedReader in = new BufferedReader(new InputStreamReader(System.in)); public static void main (String[] args) throws java.lang.Exception { String s; while ((s = in.readLine()) != null) { long k = Long.parseLong(s); System.out.println(k ^ (k >> 1)); } } } |
Решение
Рассмотрим биты числа [latex]n[/latex] и биты числа [latex]G(n)[/latex]. Заметим, что [latex]i[/latex]-ый бит [latex]G(n)[/latex] равен единице только в том случае, когда [latex]i[/latex]-ый бит [latex]n[/latex] равен единице, а [latex]i+1[/latex]-ый бит равен нулю, или наоборот ([latex]i[/latex]-ый бит равен нулю, а [latex]i+1[/latex]-ый равен единице). Таким образом, имеем: [latex]G(n) = n \oplus (n>>1)[/latex], где [latex]\oplus[/latex] — операция «побитовое исключающее ИЛИ», а [latex]>>[/latex] — «побитовый сдвиг вправо».