Еліас Омега Кодування#5697

Еліас Омега Кодування

1 секунда

256 мегабайтів

Середня

Вступ

Код Еліаса може бути використаний для ефективного кодування додатних цілих чисел, коли немає попередньої інформації про величину чисел, які потрібно закодувати, і відомо, що ймовірність отримання великого числа менша або дорівнює ймовірності отримання малого числа. З практичних міркувань, однак, у цьому конкурсі ми встановлюємо обмеження на розмір вхідних цілих чисел. З тієї ж причини ми обмежуємо вхідне ціле число бути більшим за 1.

Еліас розробив три варіанти коду: методи кодування Еліаса гамма, Еліаса дельта та Еліаса омега. Ця задача представляє методи Еліаса гамма та Еліаса омега і вимагає реалізації коду Еліаса омега. Нижче наведено передумови, визначення та ілюстрацію задачі.

Передумови

Припустимо, що Аліса хоче передати додатне ціле число $n$ Бобу через двійковий канал, і нехай $β (n)$ позначає двійкове представлення $n$ . Якщо Боб знає $∣ β (n) ∣$ (кількість бітів, необхідних для двійкового представлення $n$ ) заздалегідь, тоді Аліса повинна використовувати $β (n)$ для передачі. З іншого боку, якщо Боб не має цієї інформації, тоді Аліса може спочатку надіслати $∣ β (n) ∣$ , використовуючи ефективне та розрізнювальне кодування, а потім вона може надіслати фактичний бета-код $F_{1} = β (n)$ F_1 = \beta(n). Кінцевий результат - це код з двома полями $⟨ F_{1}, F_{2} ⟩$ \langle F_1, F_2 \rangle.

Код Еліаса та його варіанти відрізняються способом кодування цих двох частин інформації ( $F_{1}$ F_1 та $F_{2}$ F_2). Основна відмінність між варіантами полягає в представленні $F_{1}$ F_1. Це може означати модифікації в представленні $F_{1}$ F_1. Крім того, деякі з варіантів застосовують повторення або рекурсію до представлення $F_{1}$ F_1. Ми використовуємо конкретний варіант, зазначений нижче.

Визначення

Формально, у кодуванні Еліаса гамма, додатне ціле число $n$ кодується за допомогою двох конкатенованих бітових полів. Перше поле, префікс, містить $⌊ lo g_{2} n ⌋$ \lfloor\log_2 n\rfloor бітів $0$ ( $⌊ x ⌋$ - це нижня межа $x$ ). Друге поле, постфікс, - це фактичне двійкове представлення $n$ , використовуючи $⌊ lo g_{2} n ⌋ + 1$ \lfloor\log_2 n\rfloor+1 бітів. Наприклад, двійкове представлення десяткового числа $9$ - це $1001$ . За кодуванням Еліаса $9$ кодується як $0001001$ . Перші три провідні нулі позначають, що для двійкового представлення $9$ потрібно чотири біти. Наступні чотири біти містять двійкове представлення $9$ . Код Еліаса дельта застосовує гамма-код до префікса ( $⌊ lo g_{2} n ⌋$ \lfloor\log_2 n\rfloor) гамма-коду, а код Еліаса омега застосовує рекурсію над префіксом гамма-представлення Еліаса $⌊ lo g_{2} n ⌋$ \lfloor\log_2 n\rfloor.

Ілюстрація (детальний приклад)

Щоб далі проілюструвати код Еліаса омега, розглянемо ціле число $536870907$ . Двійкове представлення цього числа - це $11111111111111111111111111011$ 1\ 1111\ 1111\ 1111\ 1111\ 1111\ 1111\ 1011, що вимагає $29$ бітів. Отже, на першому кроці воно кодується наступним чином:

$⟨ F_{1}, F_{2} ⟩ = ⟨ 0000000000000000000000000000, 11111111111111111111111111011 ⟩$ \langle F_1, F_2 \rangle = \langle 0000\ 0000\ 0000\ 0000\ 0000\ 0000\ 0000, 1\ 1111\ 1111\ 1111\ 1111\ 1111\ 1111\ 1011\rangle

де пробіли, крапки, коми та дужки вставлені для зручності читання.

Щоб підкреслити, для цього конкурсу рекурсія зупиняється, коли перше поле рекурсивного етапу містить один 0.

Розглядаючи всі біти, згенеровані всіма кроками, і використовуючи $β (n)$ для позначення двійкового представлення $n$ , ми маємо:

a. $⟨ 28 нулів, β (536870907)⟩ = ⟨ 0000000000000000000000000000, 11111111111111111111111111011 ⟩$ \langle 28\ \text{нулів}, \beta(536870907)\rangle = \langle 0000\ 0000\ 0000\ 0000\ 0000\ 0000\ 0000, 1\ 1111\ 1111\ 1111\ 1111\ 1111\ 1111\ 1011\rangle

b. $⟨⟨ 4 нулі, β (28)⟩, β (536870907)⟩ = ⟨⟨ 0000, 11100 ⟩, 11111111111111111111111111011 ⟩$ \langle \langle 4\ \text{нулі}, \beta(28)\rangle, \beta(536870907) \rangle = \langle \langle 0000, 1\ 1100\rangle, 1\ 1111\ 1111\ 1111\ 1111\ 1111\ 1111\ 1011\rangle

c. $⟨⟨⟨ 2 нулі, β (4)⟩, β (28)⟩, β (536870907)⟩ = ⟨⟨⟨ 00, 100 ⟩, 11100 ⟩, 11111111111111111111111111011 ⟩$ \langle\langle\langle 2\ \text{нулі}, \beta(4)\rangle, \beta(28)\rangle, \beta(536870907) \rangle = \langle \langle\langle 00, 100\rangle, 1\ 1100\rangle, 1\ 1111\ 1111\ 1111\ 1111\ 1111\ 1111\ 1011\rangle

d. $⟨⟨⟨⟨ 0, 10 ⟩, β (4)⟩, β (28)⟩, β (536870907)⟩ = ⟨⟨⟨⟨ 0, 10 ⟩, 100 ⟩, 11100 ⟩, 11111111111111111111111111011 ⟩$ \langle\langle\langle\langle 0, 10\rangle, \beta(4)\rangle, \beta(28)\rangle, \beta(536870907) \rangle = \langle \langle\langle\langle 0, 10\rangle, 100\rangle, 1\ 1100\rangle, 1\ 1111\ 1111\ 1111\ 1111\ 1111\ 1111\ 1011\rangle

Відкидаючи всі пробіли, крапки, коми та дужки, ми отримуємо, що код Еліаса омега для $536870907$ є: $0101001110011111111111111111111111111011$ . Цей код розрізнювальний (унікально декодований). Його можна декодувати унікальним чином і отримати назад число $536870907$ .

Умова задачі

Дано деякі додатні цілі числа в діапазоні від $2$ до $2 \times 1 0^{9}$ 2 \times 10^9, вам потрібно написати програму для отримання кодів Еліаса омега для цих чисел.

Вхідні дані

Вхід містить додатні цілі числа, кожне в окремому рядку. Кожне число знаходиться в межах від $2$ до $2000000000$ , включно. Кінець вводу позначається нулем. Вхід може містити до ста рядків.

Вихідні дані

Вихід складається з рядків, кожен з яких відповідає вхідному цілому числу, крім останнього нуля. Кожен рядок містить код Еліаса омега для кожного вхідного цілого числа. Вихід не повинен містити жодних пробілів або порожніх рядків.

Приклади

Приклад 1