Can unary code represent zero?

Yes under this entry's convention: zero is encoded as the single bit 0.

Can the repeated bits be zeros instead?

Yes, if a one terminates the run and both sides use that convention consistently.

Is unary the same as gamma coding?

No. Gamma coding combines a unary length component with additional binary information.

AI Glossary / Retrieval and knowledge systems / Intermediate

Unary code

Definition

Unary code represents an integer using a repeated bit followed by a terminating bit. In the convention used here, a nonnegative integer n becomes n ones followed by a zero. Its codeword therefore contains n + 1 bits.

What it means

Unary coding turns a number into a count that a decoder can read directly. Zero is 0, one is 10, and two is 110. The final zero marks where that number ends, allowing another number to begin immediately afterward.

This entry follows the convention used in the information-retrieval textbook associated with the worklist. Other descriptions reverse the bit values or represent a positive integer n using n − 1 repeated bits. Those choices can be valid, but their encoders and decoders must agree.

Unary is useful as a small component of larger compression methods. It is usually unsuitable for directly storing a wide range of large numbers because its length grows with the value, rather than with the number of binary digits.

How it works

To encode n, write n one bits and then write zero. To decode, count successive ones until a zero arrives. Return that count and begin counting again for the next codeword.

No complete codeword is the beginning of another complete codeword. For example, 10 cannot begin 110 because their second bits differ. This prefix property lets the decoder identify boundaries without spaces between numbers.

The decoder still needs to know when the overall sequence ends. A file format might store the number of values or the valid bit length. Padding zero bits cannot simply be treated as harmless: under this convention, each would look like another encoded zero.

In a larger code, unary may describe a length or a quotient rather than the original integer. Gamma coding, for example, uses it to describe how many offset bits follow. This confines the long run of repeated bits to a smaller quantity.

Three practical examples

A search-index codec uses a unary prefix to state the length of a following binary offset.
A teaching tool displays small counts as runs of ones, helping students see the boundary between adjacent values.
A format developer tests an encoder with zero, one and a large value to expose convention mismatches and excessive output length.

Think of it this way

Think of recording a tally with one stroke per item and drawing a different mark when the tally is finished. Someone reading several tallies can count the strokes and use the finishing marks to separate them.

The analogy explains counting and termination. Actual unary coding uses bits, and the system must specify which bit repeats, which terminates, and whether counting begins at zero or one.

Worked example

Encode the invented sequence 0, 3, 1, 2 using n ones followed by zero.

The individual codewords are 0, 1110, 10 and 110. Concatenating them produces 0111010110. The total length is 1 + 4 + 2 + 3 = 10 bits.

Decoding begins with zero ones before the first zero, so the first value is 0. The next run contains three ones, giving 3. The following runs contain one and two ones, recovering the original sequence exactly.

Now consider the single value 100. Unary requires 101 bits. Its ordinary binary representation, 1100100, contains seven bits, although a stream of variable-length binary values would need a separate boundary rule. This comparison shows unary's growth cost without pretending that raw binary digits alone provide a complete alternative file format.

Illustrative case study

The fictional BirchIndex team builds a prototype decoder for a compact postings format. Its first unit example succeeds for a single positive number, but a sequence containing zero decodes incorrectly.

The team discovers that the encoder uses n repeated bits while the decoder assumes n − 1. It documents the convention, adds examples for zero and adjacent values, and stores the sequence length separately from byte padding.

It then limits the unary component to a length prefix rather than using it directly for every document identifier. This invented case illustrates specification and boundary problems. It does not report a real compression benchmark or claim that unary is the best codec for a production search engine.

Common misconceptions and mistakes

Unary always means the same bit pattern. Both the repeated bit and the integer offset can vary by convention.
Prefix-free means no framing is needed anywhere. Codeword boundaries are clear, but the complete stream still needs an ending rule.
Simplicity guarantees good compression. A large value produces a correspondingly long run, which can overwhelm any convenience.

Business use

Unary coding matters when reviewing how a search or analytics system packs small numerical quantities. Understanding it helps teams inspect codec specifications, explain boundary errors and distinguish a complete integer representation from a prefix inside another representation.

Before adopting a format, identify expected and maximum values, the treatment of zero, termination rules and malformed-input handling. A missing terminating bit should not cause an unbounded read. Benchmark the complete codec, including metadata and decoding work, because counting a few example bits does not establish end-to-end storage or latency benefits.

Check your understanding

Under n ones followed by zero, what value does 11110 represent, and how many bits does it use?

Answer: It represents 4 and uses five bits: four ones plus the terminating zero.

Related terms

Prefix code
Golomb coding
Variable byte encoding
Integer coding
gamma code
Rice coding
bitstream
index compression

Learn next

Read gamma coding next. Encode a positive integer in binary, remove its leading one, and use unary to describe the length of the remaining offset. Keep the chosen convention visible throughout the exercise.

Sources

Christopher Manning, Prabhakar Raghavan and Hinrich Schutze, Introduction to Information Retrieval, Gamma codes: https://nlp.stanford.edu/IR-book/html/htmledition/gamma-codes-1.html

The primary textbook's unary convention and gamma construction were reviewed. The sequence, decoding trace and fictional implementation case are original illustrations. Other unary conventions are explicitly distinguished.

Previous: Ultimate sampling unit Next: Unary coding