Binary Encoding

computation

Definition

Binary Encoding

Binary encoding represents a non-negative integer as a base- string using the symbols and .

For , if

then its binary encoding is

Length

The binary length of is

Thus binary encoding is logarithmic in the numeric value:

for .

This contrasts with unary encoding, where the length is .

Complexity

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

If an algorithm loops over all values , then it performs iterations. But if is binary-encoded, then the input contains only 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 . This is the central reason for pseudo-polynomial time complexity.

Example

Compact capacity field

Let a capacity be . Its binary encoding is a followed by zeros, so it has length .

A dynamic programme that iterates over all capacity values therefore performs iterations in that dimension.

Thus the input field has length , but the induced table dimension has size .