Zigzag Encoding

Epistemic Status: Sprouting - This is a zettelkasten-style card about a concept I’m interested in remembering.

---

Zigzag encoding is a space saving encoding of integers where each positive integer $n$ is assigned to:

$$2n$$

While each negative integer $n$ is assigned to :

$$2 \cdot \lvert{n}\rvert - 1$$

This has the property that the number of bits required to store an integer is proportional to its absolute value.

Protobuf and Avro Schema both use this in their binary encodings.