Related: Elias omega coding: encoding
Elias omega coding is a universal code which can encode positive integers of any size into a stream of bits.
Given a stream of bits \$S\$, the decoding algorithm is as follows:
- If \$S\$ is empty, stop. Otherwise, let \$N=1\$.
- Read the next bit \$b\$ of \$S\$.
- If \$b=0\$, output \$N\$ and return to step 1.
- Otherwise, \$b=1\$. Read \$N\$ more bits from \$S\$, append to \$b\$, and convert it from binary to integer. This is the new value of \$N\$. Go back to step 2.
In Python-like pseudocode:
s = input() while s.has_next(): n = 1 while (b = s.next()) == 1: loop n times: b = b * 2 + s.next() n = b output(n)
If the given bit stream is
- Initially \$N = 1\$.
- Since the first bit is 1, we read 1 more bit (2 bits in total) to get the new value of \$N = 10_2 = 2\$. Now the stream is
- Proceed as the same. Read a bit (1) and \$N = 2\$ more bits to get \$N = 100_2 = 4\$. Stream:
- Read a bit (1) and \$N = 4\$ more bits to get \$N = 10101_2 = 21\$. Stream:
- Read a bit (0). Since it is 0, output the current \$N = 21\$. The stream has more bits to be consumed, so we reset to \$N=1\$ and continue. Stream:
- Read a bit (0). Output the current \$N = 1\$. The stream is empty, and decoding is complete.
The output for the input stream
Given a stream of bits which consists of zero or more Elias omega coded integers, decode into the original list of integers. You can assume the input is valid (the input stream won't be exhausted in the middle of decoding a number).
Shortest code in bytes wins.
Input => Output (empty) =>  0 =>  00 => [1,1] 00100 => [1,1,2] 101001010100 => [21,1] 1110000111100001110000 => [8,12,1,8] 1111000111000101011001011110011010100001010 => [12,345,6789]