skip to content

Why does a binary format apply ZigZag encoding to a signed integer before writing it as a varint?

level: middleimportance: nice to knowfreq 34%

answer

  1. sign should not decide the size
  2. negatives sit at the top unsigned
  3. interleave the two runs around zero
  4. 0, -1, 1, -2 become 0, 1, 2, 3
  5. one extra bit of width is the price

basics

~20 s

Two's complement puts every negative number at the top of the unsigned range, so -1 would fill ten varint bytes. ZigZag interleaves the signs, mapping 0, -1, 1, -2 onto 0, 1, 2, 3, so small magnitudes stay short.

solid answer

~40 s

A varint's length follows the magnitude of the unsigned pattern it is handed. In two's complement, -1 is all one bits, so handing it straight to a varint costs the full ten bytes even though it is a tiny number. **ZigZag** remaps signed to unsigned by interleaving: non-negative `n` becomes `2n`, negative `n` becomes `-2n - 1`. So 0, -1, 1, -2, 2 become 0, 1, 2, 3, 4 and a small negative costs the same as a small positive. The inverse is `(u >> 1) XOR -(u AND 1)`, using a logical shift. The price is one extra bit of width, which can push a large positive value into one more group, and the mapping must only be applied to fields the schema declares signed.

code

pseudocode · 7 lines
pseudocode
function zigzag_encode(n, width):                      // width in bits, e.g. 64
    sign_mask = arithmetic_shift_right(n, width - 1)   // 0 if n >= 0, all ones if n < 0
    return (n << 1) XOR sign_mask

function zigzag_decode(u):
    low_bit = u AND 1                                  // 1 when the original was negative
    return logical_shift_right(u, 1) XOR (0 - low_bit)

go deeper

for a junior

Remember the problem before the trick: in two's complement a small negative number is a huge bit pattern, so a size-follows-magnitude encoding would spend its maximum on it.

for a middle

Be able to state the mapping both ways - 0, -1, 1, -2 to 0, 1, 2, 3, 4 - and explain that the low bit of the encoded value carries the sign while the rest carries the magnitude.

for a senior

Show the failure you would actually meet: a signed and an unsigned field kind swapped between two sides, decoding silently to doubled or wrong-signed values, with no structural error raised by either end.

for a principal

Treat it as a distribution decision for the field, not a property of its type. Say what evidence would tell you the values cluster near zero, and when you would spend fixed width instead and stop thinking about it.

## Why negative numbers break a naive varint A variable-length integer spends bytes in proportion to how many significant bits the value has. That is fine for counts and lengths, which are small and non-negative. It fails badly for signed fields, because of how signed integers are represented. In **two's complement**, a negative value is the bit pattern you get by subtracting the magnitude from 2^width. For a 64-bit field, -1 is sixty-four one bits; -2 is sixty-three ones followed by a zero. Handed to a varint that only sees an unsigned pattern, -1 is an enormous number, and the encoder dutifully writes **ten bytes** for it. A field carrying temperature deltas, coordinate offsets or account adjustments - values that hover around zero and are negative half the time - would spend ten bytes on half its entries and one on the other half. ## The mapping **ZigZag** solves this by reordering the signed integers so that magnitude, not sign, decides the size. It interleaves the two runs: | Signed value | ZigZag value | |---|---| | 0 | 0 | | -1 | 1 | | 1 | 2 | | -2 | 3 | | 2 | 4 | | 2,147,483,647 | 4,294,967,294 | | -2,147,483,648 | 4,294,967,295 | The rule is: a non-negative `n` maps to `2n`, and a negative `n` maps to `-2n - 1`. Equivalently, in bit operations on a value of a given width, the encoding is `(n << 1) XOR (n arithmetic-shifted right by width - 1)`. The arithmetic shift produces a mask of all zeros for a non-negative value and all ones for a negative one, so the XOR flips the shifted bits exactly when the sign bit was set. Afterwards the result is an ordinary non-negative integer and goes through the normal varint rules. The two mechanisms are separate and composable: ZigZag decides *which* unsigned number represents a signed value, the varint decides *how many bytes* that unsigned number takes. ## The inverse, and why it is exact Decoding is `(u logical-shifted right by 1) XOR -(u AND 1)`. The low bit of the ZigZag value is the sign: `1` for negative, `0` for non-negative. Negating it yields a mask of all ones or all zeros, which flips the shifted magnitude back for negatives. The mapping is a **bijection** over the full signed range - every signed value has exactly one ZigZag image and back - so no value is lost and no two values collide, including the asymmetric extreme where the most negative number has no positive counterpart. ## What it costs - **One extra bit of width.** Doubling shifts everything up by one bit, so a positive value that previously used exactly seven bits now uses eight and spills into a second varint group. Averaged over a signed field whose values straddle zero, that is a clear win; over a field that is always positive and often large, it is a pure loss. - **It must match the declared signedness.** Applying the transform to a field the schema calls unsigned, or omitting it on one that expects it, does not fail loudly: both sides decode *something*. The reader sees roughly double the intended value, or a wildly wrong negative. This is why formats expose signed and unsigned integer kinds as distinct field types rather than as an encoder option. - **It does nothing for magnitude.** ZigZag is a reordering, not a compressor. A signed field dominated by large values gains nothing; the right answer there is a fixed-width field. ## Choosing it The test is the distribution of the field, not the presence of a minus sign in its type. Ask whether the values cluster near zero. Deltas between consecutive readings, offsets relative to a base, and score adjustments all do, and those are exactly the fields where signed-plus-variable-length pays. A signed field whose values are essentially uniform over the whole range should be fixed width, where two's complement costs the same for every value and no remapping is needed at all.

  • What does ZigZag cost a large positive value?
    One extra bit, because every value is doubled. A positive that used exactly seven, fourteen or twenty-one significant bits crosses into the next seven-bit group and costs one more byte, and a 64-bit positive at the top of the signed range reaches the ten-byte worst case. On a field that is always positive and often large, the transform is a pure loss and the field should be declared unsigned or fixed width.
  • Why do formats make signed and unsigned variable-length integers separate field kinds rather than an encoder setting?
    Because a mismatch is silent. If one side applies the transform and the other does not, both still decode a value: the reader sees roughly double the number, or a large wrong negative, with no structural error to catch. Binding the transform to the declared type means the two ends cannot disagree about it.

saying these in an interview costs you the question

  • Describes ZigZag as compressing the value rather than remapping it
  • Says a small negative costs the same as its positive twin without ZigZag
  • Applies the transform to a field the schema declares unsigned
  • Believes the mapping is free for large positive values
  • Calls ZigZag just another name for two's complement