I feel compelled to give a little explanation on the mechanism for reading a null-terminated number. Since I had to think for a moment about [whiteire]'s writeup before it made sense (and it does), I think other people can benefit from my reflections.

We are given two pieces of [Claude Shannon|information], n, which is the size of a chunk, and a long [sequence] of [binary|zeroes and ones]. It is our job to determine in this long sequence what the numbers are, the whole point being that we want to be able to tell when one number ends and another begins. All we can do with the stream of zeros and ones is read one of them at a time. Once we have read them, we proceed to the next. Remember that we are reading our bits as part of a number, from least significant bit to most significant bit, all the time keeping a sharp lookout for the terminating symbol.

The simple [algorithm] for reading a single number from the binary sequence proceeds as follows:

Read n bits. If the n bits are all 0, then proceed to step 2. Otherwise, record the n bits as part of the desired number. Repeat step 1.
Read one more bit. If this bit is 1, then record n zero bits. Return to step 1. Otherwise, this bit is 0, and we have found the end of this number. Stop, and output the number.

Now, [example]! Everyone loves examples. Let us suppose that n=2 and that we are reading the following stream:

            ABCDEFGHIJKLMNOPQRSTUVW 
            11001101010010001010110

I have labelled the bits with consecutive letters of the Roman alphabet for clarity. Bit K is 0 and bit H is 1. Let's begin. Remember, our chunks consist of two bits. I have written below in all its ASCII glory what the algorithm would do.


Our number so far    | Bits still to be read | Next operation:
---------------------+-----------------------+--------------------------
                     |ABCDEFGHIJKLMNOPQRSTUVW| Read two bits.
                     |11001101010010001010110|
---------------------+-----------------------+--------------------------
AB                   |CDEFGHIJKLMNOPQRSTUVW  | No 00 found.
11                   |001101010010001010110  | Read two bits.
---------------------+-----------------------+--------------------------
AB CD                |EFGHIJKLMNOPQRSTUVW    | 00 found.
11 00                |1101010010001010110    | Read next bit: E
---------------------+-----------------------+--------------------------
AB CD                |FGHIJKLMNOPQRSTUVW     | Bit E was 1.  Continue
11 00                |101010010001010110     | Read two bits
---------------------+-----------------------+--------------------------
AB CD FG             |HIJKLMNOPQRSTUVW       | No 00 found.
11 00 10             |1010010001010110       | Read two bits.
---------------------+-----------------------+--------------------------
AB CD FG HI          |JKLMNOPQRSTUVW         | No 00 found.
11 00 10 10          |10010001010110         | Read two bits.
---------------------+-----------------------+--------------------------
AB CD FG HI JK       |LMNOPQRSTUVW           | No 00 found.
11 00 10 10 10       |010001010110           | Read two bits.
---------------------+-----------------------+--------------------------
AB CD FG HI JK LM    |NOPQRSTUVW             | No 00 found.
11 00 10 10 10 01    |0001010110             | Read two bits.
---------------------+-----------------------+--------------------------
AB CD FG HI JK LM NO |PQRSTUVW               | 00 found.
11 00 10 10 10 01 00 |01010110               | Read next bit: P
---------------------+-----------------------+--------------------------
AB CD FG HI JK LM NO |QRSTUVW                | Bit P was 0.  STOP
11 00 10 10 10 01 00 |1010110                |

The algorithm has finished. The null-terminated number we read from the sequence in binary is 11001010100100, which read from left to right in decimal is

 

            A       B       F       H       J       M  
            1*2^0 + 1*2^1 + 1*2^4 + 1*2^6 + 1*2^8 + 1*2^11

or 1 + 2 + 16 + 64 + 256 + 2048 = 2387. Observe that bits Q through W are still in our sequence. They may form part of another number, or they may be other sort of data altogether. We don't care. We have already found the number we were searching for, thanks to the null-terminated encoding of our numbers.

This procedure is meant for humans who want to write down the number (in binary) when all they have is a long sequence of zeros and ones being shot at them, one bit at a time. As far as the practical applications that [whiteire] mentions, this algorithm is probably useless for computers. Machines would have to code their arithmetic around the specifications of null-terminated numbers and hardware. The whole point is that it can be done, very efficiently, and with no theoretical limit beyond hardware constraints on the bound of numbers representable this way.

The only source of redundant information that could be avoided by [traditional methods] or the [compound numbers] that [whiteire] mentions is one extra bit each time n zeros appear in a single chunk. Since this only happens, [law of large numbers|on average], once every 2ⁿ times we read a chunk, for a random number made up of c chunks we end up wasting about c/2ⁿ bits of space. For large n (n = 8 sounds about right) and not too many chunks, the amount of wasted space with this method is not much.

null-terminated number (idea)