1 Concept
Variable-length integer encoding is a technique for representing whole numbers with a flexible number of bytes. Instead of assigning every value the same storage size, the encoding expands or contracts based on magnitude. Small integers can therefore be stored very compactly, while larger values consume additional bytes only when needed.
This approach is useful in systems that handle many small numbers, such as serialized records, compact binary formats, and message exchanges. It is designed to reduce bandwidth and storage overhead without changing the underlying numeric value.
1.1 Definition
A variable-length integer, or varint, is an integer encoded in a sequence of one or more bytes. The encoded form carries both numeric data and information about whether more bytes follow. The exact bit layout depends on the scheme, but the general idea is that each additional byte contributes more payload bits to the final value.
Varints are not a single universal format. Different standards define different byte orders, continuation markers, and signed-number handling rules. As a result, two varint encodings may be conceptually similar while remaining incompatible in practice.
1.2 Purpose
The main purpose of variable-length encoding is compactness. When datasets contain many small integers, fixed-width types can waste space by reserving unused high-order bits. Varints avoid this by using only as much space as the value requires.
They also help improve transmission efficiency in networked systems and can reduce cache pressure in memory-constrained environments. In many implementations, the format is simple enough to decode quickly, making it attractive for high-throughput software.
1.3 Historical development
Variable-length number representations have long appeared in computing, especially in compression methods and binary file layouts. Their modern popularity grew with structured serialization systems that needed a balance between compactness and speed.
As binary protocols became more common, varints were adopted to encode message sizes, field identifiers, and frequently used small counters. Later designs refined the basic concept with signed-number mappings and explicit parsing rules to make implementations more predictable.
2 Encoding schemes
Several encoding families are used for variable-length integers. They differ in how they mark continuation, how they arrange payload bits, and how they represent signed values. The choice affects readability, interoperability, and decoding complexity.
2.1 Continuation-bit encoding
Continuation-bit encoding is one of the most common schemes. Each byte reserves one bit to indicate whether more bytes follow, while the remaining bits store part of the integer value. The number is reconstructed by combining the payload bits from each byte.
This method is widely used because it is straightforward to implement and naturally supports values of arbitrary size within a chosen limit. It is especially effective when small values dominate.
2.1.1 Byte layout
In a typical layout, the high bit of each byte acts as a continuation flag. A set flag means another byte follows; an unset flag marks the final byte. The remaining seven bits per byte carry the numeric content.
The value is assembled from the payload bits according to the format’s specified byte order, commonly with the least significant group appearing first. Other layouts exist, but the continuation-marker concept remains the same.
2.1.2 Termination rules
Termination occurs when a byte is encountered whose continuation flag indicates the end of the sequence. Decoders must know how many bytes are permitted so that malformed data does not cause endless reading.
Many implementations also require a canonical form. Under such rules, a number must use the shortest valid byte sequence, preventing multiple encodings of the same integer.
2.2 Prefix-based encoding
Prefix-based encodings use leading bits or initial byte patterns to indicate the total length or the shape of the number. Instead of a repeated continuation marker, the first portion of the stream announces how many bytes belong to the integer.
This can simplify some kinds of parsing because the decoder may determine the length early. However, prefix schemes can be less flexible than continuation-bit methods and may be more sensitive to exact format definitions.
2.3 Signed integer encoding
Signed integers require special treatment because naive variable-length encodings often favor nonnegative values. A direct binary representation can be inefficient for negative numbers or may not preserve compactness across the full signed range.
To address this, formats commonly use a mapping that transforms signed values into unsigned ones before varint encoding. This preserves efficient storage while keeping the original signed meaning recoverable.
2.3.1 Zigzag encoding
Zigzag encoding maps signed integers to unsigned integers so that values near zero remain small. Commonly, nonnegative numbers are interleaved with negative numbers in a way that places 0, -1, 1, -2, 2, and so on into a compact sequence.
This arrangement is useful because it reduces the byte cost of small negative values, which would otherwise expand significantly in many encodings.
2.3.2 Two's complement considerations
Two's complement is the dominant binary representation for signed integers in modern computers, but raw two's complement bits are not always suitable for varint storage. If encoded directly, negative values may appear very large due to sign extension.
For that reason, many systems either avoid direct two's complement varints or restrict them to fixed-width interpretations. Where direct signed encoding is used, careful specification is needed to prevent ambiguity across implementations.
3 Decoding process
Decoding a varint involves reading bytes sequentially, extracting payload bits, and rebuilding the integer value. The decoder must also determine when the sequence ends and whether the input is valid.
Because the size is not fixed in advance, robust decoders are designed to stop at the proper boundary and reject malformed or overly long inputs.
3.1 Bitwise reconstruction
The decoder typically shifts each payload group into the correct position and combines it with previously read bits. In continuation-bit schemes, each new byte contributes a successive chunk of the number.
This process is usually inexpensive for small integers, but it can become more involved for large values or when the format uses unusual bit ordering. Implementations often use integer arithmetic and bitwise operations to keep the process efficient.
3.2 Error detection
Error detection is important because a malformed byte sequence can mimic a valid value or fail to terminate. Decoders commonly check for invalid continuation patterns, excessive length, or prohibited encodings.
Some formats also define canonicality checks. These reject alternate representations that would decode to the same number, helping preserve consistency and preventing duplicate forms.
3.3 Overflow handling
Overflow occurs when the encoded value exceeds the range that the target type can hold. Since varints may be used for values larger than a particular language or platform integer type, implementations must guard against truncation.
A careful decoder detects overflow before it corrupts the result. Depending on the system, it may raise an error, clamp the value, or switch to a larger numeric type.
4 Properties
Variable-length integers have a distinct set of tradeoffs. Their strengths lie in compactness and adaptability, while their limitations involve irregular parsing and potential complexity in ordering or validation.
4.1 Space efficiency
Space efficiency is the defining property of varints. Values that would be overrepresented in fixed-width storage can often be encoded in one or two bytes instead of four, eight, or more.
The benefit is greatest when the data distribution is skewed toward small magnitudes. If most numbers are large, the savings diminish, and the overhead of continuation markers may reduce the advantage.
4.2 Performance characteristics
Varints are often fast for small values because fewer bytes need to be read and processed. This can improve throughput in many practical workloads, especially where short identifiers and small counters are common.
However, performance is less predictable than with fixed-length integers. Decoders may need branching logic and looped byte processing, which can be slower in tight inner loops or less favorable for vectorized computation.
4.3 Lexicographic ordering
A varint’s byte sequence does not always preserve numeric order when compared lexicographically. Because length varies, shorter encodings may sort before or after longer ones in ways that do not match the underlying integer values.
Some encoding families are designed to improve order preservation, but ordinary varints usually prioritize compactness over sortable byte order. Applications that require direct byte-wise ordering often need additional transformations.
5 Applications
Variable-length integers appear in many binary systems that need compact numeric representation. They are especially common in serialization, where many fields may be small and numerous.
5.1 Data serialization formats
Serialization formats use varints to store integers in a space-conscious way. This is common for message schemas, structured objects, and compact interchange protocols.
Because serialization often involves repeated field counts, tags, and lengths, varints can produce significant size reductions without adding much decoding burden.
5.1.1 Protocol buffers
Protocol buffers uses variable-length integer encoding for several numeric field types, especially unsigned values and certain signed forms. The format benefits from small integers being encoded in few bytes, which is well suited to typical message data.
Its design also pairs varints with field tags and length-delimited sections, making the encoding practical for efficient parsing and schema-driven communication.
5.1.2 BSON and similar formats
BSON and related binary document formats use compact numeric encodings for metadata and lengths, though specific integer handling varies by standard. In such systems, variable-length techniques can reduce overhead in nested structures and frequently repeated counts.
These formats often combine fixed-width numeric fields with length prefixes or other compact representations, depending on what best fits the document model.
5.2 File formats
Many binary file formats use varints for sizes, indexes, offsets, or count values. This is especially useful when a format stores many small records or nested elements whose lengths differ widely.
Compact integer encoding can make files smaller and easier to stream. It can also help parsers determine record boundaries without committing to a large fixed-width field for every count.
5.3 Network protocols
Network protocols often use varints for message lengths, sequence numbers, or control information. Compact representations reduce packet size, which can matter in latency-sensitive or bandwidth-constrained environments.
They are particularly useful when a protocol needs to send numerous small numeric values in repetitive traffic. In such cases, a varint can lower overhead while still supporting larger values when necessary.
6 Implementation concerns
Implementing varints correctly requires attention to numeric limits, byte order, malformed input, and security. Small differences in specification can cause incompatibility across languages or platforms.
6.1 Language-specific representations
Different programming languages handle integers differently. Some provide arbitrary-precision types, while others rely on fixed-width signed or unsigned integers. This affects how far a varint can be decoded safely.
Developers must match the target type to the expected range of the encoding. When the source data may exceed native limits, a larger integer type or explicit range checking is needed.
6.2 Endianness
Endianness matters less for byte-at-a-time parsing than for direct multi-byte memory interpretation, but it still influences how payload bits are assembled. Some varint schemes effectively use a byte order that is independent of machine endianness, while others are defined around a specific reconstruction order.
Implementations should follow the format specification rather than relying on host architecture behavior. This avoids portability problems between systems with different internal representations.
6.3 Security considerations
Because varints are decoded from untrusted input in many settings, security concerns are important. A decoder that assumes well-formed data may read too long, miscompute values, or consume excessive resources.
6.3.1 Malformed input handling
Malformed input can include missing termination, excessive length, invalid prefix patterns, or noncanonical forms. A robust decoder should reject these cases cleanly and avoid undefined behavior.
Clear error reporting is useful both for debugging and for defending against input that intentionally violates the format.
6.3.2 Denial-of-service risks
Attackers may exploit poorly bounded decoding loops by sending long or never-ending sequences. Even if the data is ultimately invalid, repeated byte processing can waste CPU time and memory.
Defensive implementations limit the maximum byte count, cap parsed widths, and fail quickly when a sequence exceeds the allowed range. These checks help prevent resource exhaustion.
7 Comparison with fixed-length integers
Varints and fixed-length integers solve different problems. Fixed-width types are simpler and more predictable, while variable-length formats prioritize compactness for smaller values.
7.1 Advantages
The major advantage of varints is reduced storage for small numbers. They also decrease transmission size and may improve efficiency in data-heavy systems where many encoded values are short.
Varints can be especially appealing in schemas with uneven distributions, where a few large values coexist with many small ones. In that setting, the average byte cost can be significantly lower than with fixed-width fields.
7.2 Disadvantages
The main disadvantages are parsing complexity and less predictable performance. Since the number of bytes is not known in advance, decoders must inspect each byte until the value ends.
They also complicate random access and bytewise sorting. In addition, poor specification or implementation can create interoperability problems, especially across languages with different integer ranges.
7.3 Use-case tradeoffs
Varints are best suited to compact binary formats, message protocols, and datasets where small integers dominate. Fixed-length integers are preferable when constant-time access, simple alignment, or straightforward ordering matters more than space savings.
The right choice depends on the expected data distribution and the surrounding system design. Many formats use both approaches, selecting varints for some fields and fixed-width numbers for others.