The Bijection Between Natural Numbers and Binary Strings

05 Jun, 2025

Computers fundamentally operate on bits and sequences of bits. It is therefore useful to study the associated mathematical structure of the concept of sequences of bits. In this blogpost we give a brief introduction to the mathematical concept of finite binary strings and it's relation to the natural numbers.

We write a binary string of length n as $x=x_1{x}_2...x_n$ where $x_i\in \{0,1\}$.

We define the concatenation of two binary string $x=x_1...x_n$ and $y=y_1...y_m$ as $xy=x_1...x_n{y}_1...y_m$.

Let ${\mathbf{\text{B}}}^{*}=\{ϵ,\mathit{\text{0}},\mathit{\text{1}},\mathit{\text{00}},\mathit{\text{01}},\mathit{\text{11}},\mathit{\text{000}},...\}$ the set of all finite binary strings with $ϵ$ the empty string. We call $l$ the length of a binary string, i.e. $l(\mathit{\text{00}})=2$.

Let $B:{\mathbf{\text{N}}}^{+}\to {\mathbf{\text{B}}}^{*}$ be the function that takes a number and returns its binary representation, i.e. $B(4)=\mathit{\text{100}}$.

$B$ by itself won't give us a bijection because we can't match binary strings like $ϵ$ or $\mathit{\text{00}}$.

To get a bijection we have to use the following function from ${\mathbf{\text{N}}}_0$ to ${\mathbf{\text{B}}}^{*}$

This function simply adds one to the number $n$, than represents $n$ as a binary and takes the substring from the second character on. The first character is always a one and we drop it.

For example we have $⟨3⟩=B(4{)}_{2:3}=00$ or $⟨0⟩=B(1{)}_{2:1}=ϵ$ where we use the convention that a slice $x_{i:j}$ with $i>j$ is empty.

We now proof that the mapping above is indeed bijective:

Injective: Suppose $⟨x⟩=⟨y⟩$, this would mean $B(x+1{)}_{2:l_x}=B(y+1{)}_{2:l_y}$. This can only be the case when $l(x)=l(y)$. But than equality would mean that $B(x+1)=B(y+1)$ because both have the same leading one as first char. That implies $x+1=y+1$ because the binary representation of a number is unique. Therefore we can conclude that $⟨n⟩$ is injective.

Surjective: Let $x$ be an arbitrary binary string. Concatenate this string with $\mathit{\text{1}}$ from the left side and call this string $y$. The natural number which fulfils $B(n+1)=y$ is the number that fulfils $⟨n⟩=x$.

More formally we may define the inverse as

$b:{\mathbf{\text{B}}}^{*}\to {\mathbf{\text{N}}}^{+}$ is the natural mapping that interprets the binary string $\mathit{\text{1}}x$ as a natural number.

Example:

$x=\mathit{\text{101}}$, $l(\mathit{\text{101}})=3$

$b(\mathit{\text{101}})=2^{3-1}·1+2^{3-2}·0+2^{3-3}·1=5$.

Note that $0\le b(x)$ because the min value is obtained iff all $x_i$ are $\mathit{\text{0}}$

Note that $b(x)\le 2^{l(x)}{\sum }_{i=1}^{l(x)}{2}^{-i}=2^{l(x)}(1-2^{-l(x)})=2^{l(x)}-1$ because the maximum value is obtained iff all $x_i$ are $\mathit{\text{1}}$

We have $b(\mathit{\text{1}}x)=2^{l(x)}+b(x)$ and therefore $2^{l(x)}-1\le b(\mathit{\text{1}}x)-1$. Furthermore we have $b(\mathit{\text{1}}x)-1\le 2^{l(x)}+2^{l(x)}-1-1=2^{l(x)+1}-2$.

This gives us an effective bound for $⟨x{⟩}^{-1}$:

This shows that the range in which a number associated with a binary string is determined solely by the length of the binary string.

Note that the above bijection is often used in literature such that we write $l(n)$ for $l(⟨n⟩)$ and $x+1$ instead of $⟨x{⟩}^{-1}+1$ if clear from the context. It also gives us a way to enumerate all binary strings.