ZigZag encoding

As we saw in the previous section, int32 and int64 are not efficient at storing negative numbers. They will always result in 10-byte-long payloads. To solve this specific use case of negative numbers, Protobuf introduces two other types: sint32 and sint64. The “s” stands for signed and they handle negative numbers.

The reason why they handle negative numbers more efficiently is that they add an extra step on top of varint encoding. This extra step, called ZigZag encoding, consists of turning all negative numbers into positive ones, and because varint encoding is very good at encoding positive numbers, we solved the problem.

Now, as usual, let’s see an example of ZigZag encoding. Let’s take our cherished 128. We have the following binary:

00000000 10000000

Now, let’s left shift by one:

00000001 00000000

We will then take the original binary and apply a right shift of 31 in the case of int32 and 63 in the case of int64...