Binary Encoding

computation

Definition

Binary Encoding

Binary encoding represents a non-negative integer $n$ as a base-$2$ string using the symbols $0$ and $1$.

For $n>0$, if

$$n=\sum _{i=0}^k{b}_i{2}^i\text{with }{b}_i\in \{0,1\}\text{ and }{b}_k=1,$$

then its binary encoding is

$$b_k{b}_{k-1}\cdots b_0.$$

Length

The binary length of $n$ is

$$\ell (n)=\lceil {\log }_2(n+1)\rceil .$$

Thus binary encoding is logarithmic in the numeric value:

$$|\mathrm{bin}(n)|=\Theta (\log n)$$

for $n\ge 2$.

This contrasts with unary encoding, where the length is $\Theta (n)$.

Complexity

Binary encoding is compact. A number can be exponentially larger than its representation length.

If an algorithm loops over all values $0,1,\dots ,W$, then it performs $\Theta (W)$ iterations. But if $W$ is binary-encoded, then the input contains only $\Theta (\log W)$ bits for this value.

Hence such an algorithm may be exponential in the encoded input length even though it is polynomial in the numeric value $W$. This is the central reason for pseudo-polynomial time complexity.

Example

Compact capacity field

Let a capacity be $W=2^L$. Its binary encoding is a $1$ followed by $L$ zeros, so it has length $L+1$.

A dynamic programme that iterates over all capacity values $0,1,\dots ,W$ therefore performs $2^L+1$ iterations in that dimension.

Thus the input field has length $O(L)$, but the induced table dimension has size $\Theta (2^L)$.