skip to content

How does a base-128 varint use the top bit of each byte to encode an integer whose width the reader does not know in advance?

level: middleimportance: must knowfreq 62%

answer

  1. self-delimiting number, no separate length
  2. one flag bit per byte
  3. seven payload bits, eighth is the flag
  4. top bit set means keep reading
  5. least-significant group first

basics

~20 s

A base-128 varint carries seven payload bits per byte and spends the eighth as a continuation flag: set means another byte belongs to this number, clear means this is the last one. The reader stops at the first byte whose top bit is clear.

solid answer

~40 s

Each byte of a varint is split seven-plus-one. The low seven bits carry one group of the value; the top bit is the continuation flag, `1` for 'more bytes follow' and `0` for 'this is the final byte'. Groups are emitted least-significant first, so the decoder accumulates `(byte AND 0x7F) << shift` and adds seven to `shift` per byte. That makes the number **self-delimiting**: no separate length field is needed in front of it, and a value can sit immediately before the next field. The consequence for size is that magnitude, not declared width, sets the cost: 0-127 fits in one byte, values up to 16,383 in two, and a full 64-bit value needs ten.

code

pseudocode · 10 lines
pseudocode
function decode_varint(stream):
    result = 0
    shift = 0
    repeat
        b = stream.next_byte()
        payload = b AND 0x7F           // low seven bits carry the group
        result = result + (payload << shift)
        shift = shift + 7
    until (b AND 0x80) = 0             // top bit clear ends the number
    return result

go deeper

for a junior

Recall the shape: seven bits of number per byte plus one flag bit that says whether the number continues. That alone explains why a small count takes a single byte on the wire.

for a middle

Be able to encode and decode a small value by hand - 300 becomes AC 02 - and explain the accumulate-and-shift loop, including why the groups arrive least-significant first.

for a senior

Show where the encoding stops paying: high-entropy 64-bit values costing nine or ten bytes, the loss of offset arithmetic, and the per-byte branch on a hot decode path. Say which fields in a real layout you would leave fixed width.

for a principal

Frame it as a distribution question. The encoding is a bet that values cluster near zero; state the bet, say what measurement would settle it for your data, and decide where a mixed layout is worth its extra rules.

## What a varint is for A **base-128 varint** writes a non-negative integer in a number of bytes that depends on the **value's magnitude**, not on the width the field was declared with. Most integers that real records carry are small - field lengths, counts, small identifiers, enumerated choices - so a layout that spends eight bytes on every 64-bit integer wastes most of them on leading zero bits. The varint exists to stop paying for those zeros, and it does so without adding a separate size field in front of each number. ## The byte layout Every byte of a varint splits into two parts: - the **low seven bits** carry one slice of the value, called a **group**; - the **top bit** is the **continuation bit**: `1` means at least one further byte belongs to this same number, `0` means this byte closes it. Groups are written **least-significant first**. This ordering is part of the varint definition itself, so it is not affected by the format's choice of byte order for its fixed-width fields. The continuation bit is what makes the encoding **self-delimiting**: a reader that knows nothing about the value can still tell where it ends, simply by consuming bytes until one arrives with a clear top bit. That property is why a varint can be placed directly before the next field with nothing separating them, and why it can itself serve as the length of a following field. ## Worked example: the number 300 300 in binary is `1 0010 1100`. 1. Take the low seven bits: `010 1100` = `0x2C`. More groups remain, so set the continuation bit: `0xAC`. 2. Shift the value right by seven: 300 >> 7 = 2. That is `0x02`, no further groups remain, so the continuation bit stays clear. 3. The wire bytes are `AC 02`. Decoding reverses it. `0xAC` has its top bit set, so its payload `0x2C` = 44 goes in at shift 0 and the reader continues. `0x02` has a clear top bit, so its payload 2 goes in at shift 7, contributing 2 x 128 = 256, and the number ends. 44 + 256 = **300**. ## What each width buys | Value range | Bytes on the wire | |---|---| | 0 - 127 | 1 | | 128 - 16,383 | 2 | | 16,384 - 2,097,151 | 3 | | 2,097,152 - 268,435,455 | 4 | | up to 2^56 - 1 | at most 8 | | 2^56 and above (64-bit) | 9 or 10 | The last two rows are the honest caveat. Seven bits per byte means eight bytes hold only 56 bits, so a 64-bit value that genuinely uses its top bits costs **more** than the eight bytes a fixed-width field would spend - nine bytes for 57 to 63 significant bits, ten for a full 64. Uniformly random 64-bit identifiers and digest values are exactly the case where a varint loses. ## What it costs beyond size - **No random access.** Because each field's width is discovered while reading it, a decoder cannot compute the offset of the fifth field arithmetically; it must walk the record from the start. A fixed-width layout can jump. - **A branch per byte.** The decode loop tests the continuation bit on every byte, which is a data-dependent branch, against a single aligned load for a fixed-width field. On a hot decode path that difference is measurable. - **Redundant encodings are representable.** Nothing in the byte rules forbids a trailing group of zero - `AC 82 00` also decodes to 300 - so a format that needs byte-identical output for equal values must forbid such non-minimal forms explicitly. What a format does to guarantee a single canonical byte string is a separate subject. ## When to reach for it Use a varint where the distribution is skewed toward small values and where the field is read sequentially anyway: lengths, counts, small keys, offsets that are usually near zero. Use fixed width where values are high-entropy, where the reader wants offset arithmetic or in-place access, or where the decode loop's per-byte branch shows up in a profile. A layout that mixes both deliberately - varints for lengths, fixed width for digests - is a normal and defensible design, not a compromise.

  • When does a varint cost more bytes than a plain fixed-width 64-bit field?
    Whenever the value is large. Seven payload bits per byte means eight bytes hold only 56 bits, so a value at or above 2^56 needs nine bytes and a full 64-bit value needs ten, against eight for fixed width. High-entropy fields - random identifiers, digests, hashed keys - sit in that region almost always, which is why layouts usually keep them fixed width.
  • Why can a decoder not jump straight to the fifth field of a record whose integers are varints?
    Because each field's width is only known once it has been read. Offsets are therefore not computable in advance; the decoder walks the record from the beginning, consuming each field to find where the next one starts. Fixed-width fields at known positions are what makes offset arithmetic, and with it in-place access, possible.
  • Two encoders write 300 as `AC 02` and as `AC 82 00`. Do both decode, and is that a problem?
    Both decode to 300 - the second simply adds a group of zero at shift 14. It is a problem only where equal values must produce identical bytes, for example when the bytes are hashed or signed. Formats that need that property forbid non-minimal varints rather than relying on encoders to agree.

It is a page-numbering convention where every page ends either with 'continued overleaf' or with a full stop: you never need to be told the chapter's length up front, you just keep turning until a page ends cleanly.

saying these in an interview costs you the question

  • Thinks a varint is smaller than fixed width whatever the value's magnitude
  • Says all eight bits of each varint byte carry the number
  • Assumes varint fields can be reached by offset like fixed-width ones
  • Claims a varint needs its own length prefix in front of it
  • Reads the byte groups most-significant first