What is the name of the following binary encoding?

Question

S is a the set of binary strings in Shortlex order: [0,1,00,01,10,11,...]

I want to encode / decode natural numbers with the following scheme:

Encoding N: For natural number N return the binary string with index N in S: Code(N)=S[N]

Decoding Code: Return the index of the binary string Code in S: Decode(11)=5

Can you please suggest the name of this encoding and how to implement it?

Example of Numbers and Codes:

Number | Code
0  | 0
1  | 1
2  | 00
3  | 01
4  | 10
5  | 11
6  | 000
7  | 001
8  | 010
9  | 011
10 | 100
11 | 101
12 | 110
13 | 111

Answer 1

Your encoding is not self-terminating, which makes it somewhat less useful than encodings such as universal codes.

Given an integer $n \geq 0$, write $n+2$ in binary without leading zeroes, and remove the MSB to get your encoding. In the other direction, add a leading one, and subtract $2$.

If you also allow the empty string, and you are only interested in encoding integers $n \geq 1$, then there is no need to add or subtract $2$ in the above recipe.

Answer 2

That's essentially bijective base 2. The only differences are that the set of digits used is $\{0, 1\}$ instead of $\{1, 2\}$, and that in the sequence of codes, the empty string is skipped.

As others have already suggested, you can encode a number by adding 2, writing it in binary, and removing the leading 1; and you can decode a number by adding a leading 1, decoding the result as binary, and then subtracting 2.

Answer 3

I don't know the name of this encoding, but notice that with $k$ digits you'll be able to encode exactly $2^k$ numbers. In particular, those starting from: $ \sum_{i=1}^{k-1} 2^i =2^{k}-2. $

It follows that, given an integer $n$, the number of digits of the encoding can be found as the largest value of $k$ such that $2^k \le n+2$, i.e., $k=\lfloor \log_2 (n+2) \rfloor$. Notice that $k$ is exactly one less than the number of digits needed to write $n+2$ in binary, so you can find it in time $O(\log n)$.

Then, you can also write down the actual digits in time $O(k)=O(\log n)$ by looking at the binary representation of $n-(2^k-2) = n-2^k+2$.

As an example, the encoding of $42$ consists of $k=\lfloor \log_2 (44) \rfloor = 5$ digits (since $2^5=32$ and $2^6=64$). These digits are $01100$ (notice the leading $0$) since $(42-32+2)_{10} = (12)_{10} = (1100)_2$.

---

To decode a number, you can do the reverse: count the number $k$ of digits in the encoded version, then add together $2^{k}-2$ and the number whose binary representation corresponds to the given digits. This also requires $O(k)=O(\log n)$ time.

For example, the encoded number $01100$ has $5$ digits, so the represented integer is $(2^5 -2)_{10} + (01100)_2 = (30 + 12 )_{10} =(42)_{10}$.

Answer 4

From shortlex to natural:

• add $(10_b)^l-10_b$ to the binary value, where $l$ stands for the length (number of bits).

E.g. $011_s\to l=3\to11_b+1000_b-10_b=1001_b=9$.

From natural to shortlex:

• the length is $l=\lfloor\log_2(n+2)\rfloor$,

• subtract $2^l-2$,

• fill left with zeroes.

E.g. $9\to l=\lfloor\log_2(11_d)\rfloor=3\to9-2^3+2=3=11_b\to011_s$