Back
+30 XP
Concept

ZigZag Integer Encoding / Decoding

Standard Varints represent negative integers using two's complement, bloating small numbers like -1 into 10-byte sequences. ZigZag encoding maps signed integers to positive values by interleaving positive and negative numbers, allowing small negatives to compress into 1 byte.

python
# ZigZag Encode:
encoded = (n << 1) ^ (n >> 63) if n < 0 else (n << 1)
# ZigZag Decode:
decoded = (n >> 1) ^ (-(n & 1))

# ZigZag Integer Encoding / Decoding When Google invented Protocol Buffers, they noticed an embarrassing bug with Varints. A small positive number like `1` encodes in 1 byte (`0x01`). But the signed number `-1` in 64-bit two’s complement is `0xFFFFFFFFFFFFFFFF`. Encoded as a Varint, that tiny `-1` takes **10 full bytes**! 🛑📦 **ZigZag encoding** solves this by interleaving negative and positive integers: - ` 0` $\rightarrow$ `0` - `-1` $\rightarrow$ `1` - ` 1` $\rightarrow$ `2` - `-2` $\rightarrow$ `3` - ` 2` $\rightarrow$ `4` Small numbers of either sign stay small, compressing into 1 or 2 bytes on the wire. ```python # Encoding: def zigzag_encode(n: int) -> int: return (n << 1) ^ (n >> 63) if n < 0 else (n << 1) # Decoding: def zigzag_decode(n: int) -> int: return (n >> 1) ^ (-(n & 1)) ``` ## Pop Quiz Why does raw Varint/LEB128 encoding expand -1 into 10 bytes on the wire without ZigZag transformation? - [ ] In 64-bit two's complement, -1 has all 64 bits set to 1, requiring 10 Varint 7-bit chunks to encode. - [ ] The Varint specification reserves negative integers exclusively for RPC error codes. - [ ] Negative numbers trigger a parity bit error in standard network transceivers. - [ ] Because Python converts negative integers into floating point NaN values during serialization. ## Real-World Challenge Implement `zigzag_encode(n: int) -> int` and `zigzag_decode(n: int) -> int`. - Verify that `zigzag_encode(-1) == 1`, `zigzag_encode(1) == 2`, `zigzag_encode(-2) == 3`. - Test that numbers across the 64-bit signed spectrum round-trip losslessly. <details> <summary>Solution</summary> ```python def zigzag_encode(n: int) -> int: if n < 0: return (-n * 2) - 1 return n * 2 def zigzag_decode(n: int) -> int: if n % 2 == 1: return -((n + 1) // 2) return n // 2 # Verification assert zigzag_encode(0) == 0 assert zigzag_encode(-1) == 1 assert zigzag_encode(1) == 2 assert zigzag_encode(-2) == 3 assert zigzag_encode(2) == 4 test_cases = [0, -1, 1, -2, 2, -100, 100, -2147483648, 2147483647, -9223372036854775808] for val in test_cases: enc = zigzag_encode(val) dec = zigzag_decode(enc) assert dec == val, f"Mismatch for {val}: got {dec}" assert enc >= 0 ``` </details>