1.5　ZigZag编码

1.5.1　ZigZag编码流程

ZigZag将有符号整数统一映射为无符号整数，再通过Varint编码规则达到数据压缩的效果。ZigZag的编码流程如下：

1）将整数补码最高位移到最低位。正整数的最高位为0，数值越小，高位的0越多。负整数的最高位为1，绝对值越小，高位的1越多。以整数1为例，最高位移位操作如表1-12所示。

以整数-1为例，最高位移位操作如表1-13所示。

从表1-13可以看出，负数绝对值越小，包含的前导1越多，用Varint编码压缩效果越差。

2）如果是负数，除符号位外，其他位取反；正数无须操作。这一步获得的便是ZigZag编码。以整数1为例，ZigZag编码的过程如表1-14所示。

以整数-1为例，ZigZag编码的过程如表1-15所示。

0的ZigZag编码和补码一致，读者可自行验证。

至此，正整数、0、负整数都可以用ZigZag编码来表示了。

1.5.2　ZigZag编码算法实现

ZigZag编码算法实现如以下代码所示。

上述代码看起来并不太好理解，下面通过步骤分解的方式来分析代码要表达的意思，如表1-16所示。

1）n ＜＜ 1：表示将整个值左移1位，正数、0、负数的最后1位就变成了0。

2）n ＞＞ 31：符号位放到最后1位。如果是非负数，则为全0；如果是负数，就是全1。

3）异或操作后可以看到，数据位全部反转了，而符号位保持不变，且移动到了最后1位。

1.5.3　ZigZag反编码流程

ZigZag反编码流程如下：

1）如果最低位是1，表示是负数，除符号位外，其他位取反；如果最低位是0，表示是正数，无须操作。以整数1为例，ZigZag反编码如表1-17所示。

以整数-1为例，ZigZag反编码如表1-18所示。

2）将整数补码最低位移到最高位。以整数1为例，最低位移位操作如表1-19所示。

以整数-1为例，最低位移位操作如表1-20所示。

1.5.4　ZigZag反编码算法实现

ZigZag编码还原为整数的算法实现如以下代码所示。

上述代码看起来也不太好理解，依然通过步骤分解的方式来分析代码要表达的意思，如表1-21所示。

1.5.5　总结

ZigZag编码使用的前提是：在大多数情况下使用的数字都是小整数，比如用户年龄、班级、年级、购物数量等。当数字比较大的时候，需要5字节来表示整数。ZigZag编码机制被用于Thrift、Protocol Buffer、Avro等序列化方案中。