ZigZag Encoding
ZigZag encoding maps signed integers to unsigned integers so that negative numbers of small magnitude also occupy few bytes; combined with Varint it yields efficient variable-length coding.
Purpose
It makes small negative numbers (such as -1) as compact as small positive ones under variable-length encoding, avoiding the expansion caused by all-1 high bits in two's complement.
Mechanism
The mapping rule: n ≥ 0 → 2n, and n < 0 → 2|n| - 1 — that is, 0→0, -1→1, 1→2, -2→3, 2→4... Integers alternate by absolute value, so small values map to small unsigned numbers.
Use cases
- Protobuf sint32/sint64 encoding
- Compact signed integer serialization
- Variable-length signed columns in databases