Enumeration of Binary Strings

Suppose we want to encode the natural numbers as bit strings as follows:

0 = λ // the empty string
1 = 0
2 = 1
3 = 00
4 = 01
5 = 10
6 = 11
7 = 000
8 = 001
9 = 010
10 = 011
11 = 100
12 = 101
13 = 110
14 = 111
15 = 0000
...


How can we calculate the encoding of any given number? For example, how do I calculate the encoding of 173?

My professor stated that this method works:

Given a number x, add a “1” to the beginning of x, calculate the number that 1x encodes in binary, then subtract 1 from the answer.

However, I have failed to get this to work.

Any help is much appreciated.

For a given value $$n$$ calculate $$m= \lfloor \log_2(n+1) \rfloor$$ so $$\begin{eqnarray*} 2^{m}-1 \leq n \leq 2^{m+1}-2. \end{eqnarray*}$$ Now subtract $$2^{m}-1$$ from $$n$$ $$\begin{eqnarray*} 0 \leq n'= n -2^{m}-1 \leq 2^{m}-1. \end{eqnarray*}$$ Now give the $$m$$ digit binary representation of $$n'$$ (and include zeros for the larger digits which would have otherwise not been included.)

Observe that the encoding of (n) is given by removing the initial (1) from the string that is (n+1) in binary (base 2).

We can obtain the binary form of a number in several ways: one such algorithm is as follows. - Initialise an empty string. - While the number you have is more than zero, do the following: - if it is odd, subtract one from it and then halve it; then append 1 to the string. - if it is even, halve it and append 0 to the strong. - Reverse the string; it now holds the binary form of the original number.

To get your encoding, simply find the binary form of (n+1) using that algorithm and then remove the first digit from it; if you wish to do this directly, you can simply change the condition in the while block to be "while the number is more than one", and then output the result of that algorithm.

• I just realized a typo in my original question... 0 is encoded as λ, 1 as 0, 2 as 1, 3 as 00... I have updated my question to reflect this – kjmj Oct 10 '18 at 22:15
• @kjmj I've edited by answer to match. – Benedict Randall Shaw Oct 11 '18 at 6:54
• Thank you for this, its quite amazing you were able to come up with something like this. I have posted another version of a way to solve my original question – kjmj Oct 11 '18 at 16:15

Clarified this with my professor today. The method is simple:

Bit-string -> Number: Prepend 1 to the bit string, decode from binary, subtract 1

Number -> Bit-string: Add 1 to the number, encode as binary, eliminate the initial 1