Standard Varints are great for positive numbers, but they are highly inefficient for negative ones. ZigZag encoding fixes this.
Two's complement stores the sign in the most significant bit. That means every negative number has its high bits set. That's bad news for varints. They save space by dropping leading zeros, and a negative number doesn't have any to drop. Even -1 takes the full 10 bytes of a 64-bit varint.
ZigZag encoding moves the sign to the least significant bit instead. Positive numbers map to even integers (n << 1) and negative numbers to odd ones.
With the sign at the bottom, small negative numbers have leading zeros again and encode as compactly as small positive ones.
The name comes from how the mapping alternates between positive and negative as the encoded value counts up. 0 maps to 0, -1 to 1, 1 to 2, -2 to 3, 2 to 4, and so on.
In a schema, ZigZag is what sint32 and sint64 select. The Types reference covers when to reach for those over plain int32 and int64.
The encoder below shows the mapping bit by bit. Pick a number and watch where the sign lands.
Standard Varint (Two's Complement)
10 Byte(s)As a plain varint, -1 takes all 10 bytes: a negative number has no leading zeros to drop.
ZigZag Varint
1 Byte(s)After ZigZag, size depends on the number's magnitude rather than its sign: -1 encodes in a single byte, and the byte count grows only as the value moves away from zero.
Further Reading
- Protobuf Tip #10: Choosing the right integer type
When sint32 and sint64, the types that select ZigZag, actually pay off.
Next
The Field Tag
How Protobuf packs a field number and wire type into a single tag byte, with an interactive calculator that shows the bit layout for any field.