엘리아스 오메가 부호화

엘리아스(Elias) 부호는 부호화할 양의 정수의 크기에 대한 사전 정보가 없고, 작은 정수가 나올 확률이 큰 정수가 나올 확률보다 크거나 같다고 가정할 때 정수를 효율적으로 부호화하는 접두 부호이다. 이 문제에서는 정수의 크기에 상한을 두며, 부호화할 모든 정수는 $1$보다 크다.

엘리아스는 세 가지 변형인 엘리아스 감마(gamma), 델타(delta), 오메가(omega) 부호를 정의했다. 이 문제에서는 감마 부호와 오메가 부호를 소개하고, 엘리아스 오메가 부호를 구현하도록 요구한다.

양의 정수 $n$의 이진 표현을 $\beta(n)$이라 하자(가장 앞 비트는 항상 $1$이다). 그리고 그 비트 수를 $|\beta(n)|$이라 하자. 수신자가 $|\beta(n)|$을 미리 안다면 송신자는 $\beta(n)$만 보내면 된다. 모른다면 먼저 그 길이를 스스로 구분 가능한(self-delimiting) 방식으로 보내야 하며, 각 변형은 이 길이를 부호화하는 방법에서 차이가 난다.

엘리아스 감마. 양의 정수 $n$은 이어 붙인 두 필드로 표현된다. 앞부분(prefix)은 $\lfloor \log_2 n \rfloor$개의 $0$ 비트이고, 뒷부분은 $\lfloor \log_2 n \rfloor + 1$개의 비트를 차지하는 $\beta(n)$이다. 예를 들어 $\beta(9) = 1001$이므로 $9$의 감마 부호는 $0001001$이다. 앞의 $0$ 세 개는 뒤에 네 비트가 온다는 뜻이고, 그 네 비트가 $\beta(9)$이다.

엘리아스 오메가. 오메가 부호는 앞부분에 $0$을 나열하는 대신 그 길이를 재귀적으로 부호화한다. $\lfloor \log_2 n \rfloor = |\beta(n)| - 1$로 두면, 오메가 부호는 다음과 같이 정의된다.

$\mathrm{code}(n) = \begin{cases} 0\,\beta(n), & \lfloor \log_2 n \rfloor = 1 \text{ 인 경우} \\ \mathrm{code}\!\left(\lfloor \log_2 n \rfloor\right)\,\beta(n), & \text{그 외의 경우} \end{cases}$

즉, 어떤 단계의 앞부분에 필요한 $0$이 하나뿐이 되는 순간 재귀가 멈춘다.

예를 들어 $536870907$을 살펴보자. 그 이진 표현 $\beta(536870907)$은 $29$비트가 필요하다. 단계별로 부호를 만들면($\beta(2)=10$, $\beta(4)=100$, $\beta(28)=11100$):

$0 \;\; 10 \;\; 100 \;\; 11100 \;\; \beta(536870907).$

모두 이어 붙이면 엘리아스 오메가 부호

$0101001110011111111111111111111111111011$

를 얻으며, 이는 유일하게 복호화되어 $536870907$로 되돌아간다.

여러 개의 양의 정수가 주어질 때, 각 정수의 엘리아스 오메가 부호를 출력하여라.

각 줄에는 $2 \le n \le 2{,}000{,}000{,}000$을 만족하는 양의 정수 $n$이 하나씩 주어진다. $0$이 적힌 줄은 입력의 끝을 나타내며 부호화하지 않는다. 종료용 $0$ 앞에 오는 정수는 최대 $100$개이다.

입력의 각 정수에 대해(종료용 $0$은 제외) 그 엘리아스 오메가 부호를 입력 순서대로 한 줄에 하나씩 출력한다. 출력에는 공백이나 빈 줄이 없어야 한다.