ZigZag Integer Encoder

ZigZag encoding is the trick Protocol Buffers uses to store signed integers efficiently. Negative numbers in two’s complement have all their high bits set, which would waste bytes in a varint. ZigZag remaps the signed range so that small magnitudes — whether positive or negative — become small unsigned values that pack into one or two bytes.

How it works

For an n-bit value the encoding interleaves negatives and non-negatives:

encoded = (value << 1) XOR (value >> (n - 1))

  0 ->  0
 -1 ->  1
  1 ->  2
 -2 ->  3
  2 ->  4

The left shift by one frees the lowest bit to carry the sign, while the arithmetic right shift by n - 1 smears the original sign bit across the whole word so the XOR flips the right bits. Decoding inverts it with (encoded >> 1) XOR -(encoded AND 1): the masked low bit reconstructs the sign and the right shift restores the magnitude.

The varint problem ZigZag fixes

To understand why ZigZag exists, you need to understand Protocol Buffers’ variable-length integer (varint) encoding. Varints use 7 bits of each byte to encode the value, with the 8th bit indicating whether more bytes follow. This lets small unsigned numbers pack into a single byte (values 0–127) and medium values into two bytes (128–16,383), making the common case very compact.

The problem is two’s complement for signed integers. The integer −1, in two’s complement, is represented as all bits set: 0xFFFFFFFF for 32-bit. Encoded as a varint, this would require the full 5 bytes (or 10 bytes for 64-bit), since all the high bits are set. Every small negative number has the same problem.

ZigZag sidesteps this by first mapping the signed integer to a non-negative integer with small magnitude, then encoding that with varint. Because the resulting unsigned value is small, varint encodes it compactly:

When to use sint32 vs sint64

Protocol Buffers uses two field types for ZigZag-encoded integers: sint32 and sint64. The choice should match the range of values your field will hold:

• Use sint32 for values that fit in a 32-bit signed integer (roughly −2 billion to +2 billion). The ZigZag range is 0 to 4,294,967,295 for the encoded value.
• Use sint64 for larger ranges. The encoded value fits in an unsigned 64-bit integer.

Using sint64 for values that always fit in sint32 wastes nothing — ZigZag still encodes small values into small varint representations regardless of the declared width. But sint32 is clearer about the expected range and serves as documentation for other developers.

Note that int32 and int64 (the protobuf types without the s prefix) do not use ZigZag encoding. If you use int32 to store negative values, Protocol Buffers always encodes them as 10-byte varints because the two’s complement form is treated as a large positive number. Always use sint32/sint64 when your field can hold negative values.

Tips and notes

Select the width that matches your protobuf field: sint32 uses 32-bit ZigZag, sint64 uses 64-bit. The encoder enforces the signed range for the chosen width, and the decoder expects a non-negative encoded value. ZigZag is usually the first step before varint encoding — encode the signed number here, then feed the resulting unsigned value into the varint tool to get the final wire bytes.