Enumeration of Binary Strings

Question

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.

Answer 1

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

Answer 2

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.

Answer 3

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.)