Элиас Омега Кодирование
Введение
Код Элиаса используется для эффективного кодирования положительных целых чисел, особенно когда нет предварительной информации о величине кодируемых чисел, и вероятность появления больших чисел меньше или равна вероятности появления малых. Однако, в этом конкурсе мы ограничиваем размер входных целых чисел по практическим соображениям. Также мы ограничиваем входные числа значениями больше 1.
Элиас разработал три варианта кодирования: гамма, дельта и омега. В этой задаче рассматриваются методы кодирования Элиаса гамма и омега, и требуется реализовать код Элиаса омега. Ниже приводится предыстория, определение и иллюстрация задачи.
Предыстория
Предположим, что Алиса хочет передать положительное целое число n Бобу через двоичный канал, и пусть β(n) обозначает двоичное представление n. Если Боб заранее знает |β(n)| (количество бит, необходимых для двоичного представления n), то Алиса должна использовать β(n) для передачи. В противном случае, если у Боба нет этой информации, Алиса может сначала отправить |β(n)| с использованием эффективного и различимого кодирования, а затем передать фактический бета-код F_1= β(n). Конечный результат — это код из двух частей < F_1, F_2 >.
Код Элиаса и его варианты различаются способом кодирования этих двух частей информации (F_1 и F_2). Основное различие между вариантами заключается в представлении F_1. Это может включать изменения в представлении F_1. Кроме того, некоторые варианты применяют повторение или рекурсию к представлению F_1. Мы используем конкретный вариант, указанный ниже.
Определение
Формально, в кодировании Элиаса гамма положительное целое число n кодируется с использованием двух объединенных битовых полей. Первое поле, префикс, содержит [log_2n] битов 0 ([x] — это нижняя граница x). Второе поле, постфикс, — это фактическое двоичное представление n, используя [log2 n]+1 бит. Например, двоичное представление десятичного числа 9 — это 1001. В кодировании Элиаса 9 кодируется как 0001001. Первые три ведущих нуля указывают, что для двоичного представления 9 требуется четыре бита. Следующие четыре бита содержат двоичное представление 9. Код Элиаса дельта применяет гамма-код к префиксу ([log_2n]) гамма-кода, а код Элиаса омега применяет рекурсию к префиксу гамма-представления Элиаса [log_2n].
Иллюстрация (подробный пример)
Чтобы дополнительно проиллюстрировать код Элиаса омега, рассмотрим целое число 536870907. Двоичное представление этого числа — это 1 1111 1111 1111 1111 1111 1111 1011, что требует 29 бит. Следовательно, на первом шаге оно кодируется следующим образом:
< F_1, F_2 > = < 0000 0000 0000 0000 0000 0000 0000, 1 1111 1111 1111 1111 1111 1111 1011>
где пробелы, точки, запятые и скобки вставлены для удобства чтения.
Для акцента, в этом конкурсе рекурсия останавливается, когда первое поле рекурсивного этапа содержит один 0.
Рассматривая все биты, сгенерированные на всех этапах, и используя β(n) для обозначения двоичного представления n, мы имеем:
a. <28 нулей, β(536870907)> = < 0000 0000 0000 0000 0000 0000 0000, 1 1111 1111 1111 1111 1111 1111 1011>
b. < <4 нуля, β(28)>, β(536870907) > = < <0000, 1 1100>, 1 1111 1111 1111 1111 1111 1111 1011>
c. «<2 нуля, β(4)>, β(28)> , β(536870907) > = < «00, 100>, 1 1100>, 1 1111 1111 1111 1111 1111 1111 1011>
d. «<, β(4)>, β(28)>, β(536870907 ) > = < «<0, 10>, 100>, 1 1100>, 1 1111 1111 1111 1111 1111 1111 1011>
Убирая все пробелы, точки, запятые и скобки, мы получаем, что код Элиаса омега для 536870907 — это: 0101001110011111111111111111111111111011. Этот код различим (однозначно декодируем). Он может быть декодирован уникальным образом и вернуть число 536870907.
Условие задачи
Даны некоторые положительные целые числа в диапазоне от 2 – 2×10^9, вам нужно написать программу для получения кодов Элиаса омега для этих чисел.
Входные данные
Вход содержит положительные целые числа, каждое в отдельной строке. Каждое число находится в диапазоне от 2 - 2000000000, включительно. Конец ввода обозначается нулем. Ввод может содержать до ста строк.
Выходные данные
Вывод состоит из строк, каждая из которых соответствует входному целому числу, за исключением последнего нуля. Каждая строка содержит код Элиаса омега для каждого входного целого числа. Вывод не должен содержать пробелов или пустых строк.