1.4　Varint编码

很多时候用到的整数往往是比较小的。比如，人的年龄，大多数都在100以内；再比如，学校有几个年级，一个年级有几个班，基本都在20以内。这些小整数在计算机里和相同类型的大整数占用相同的字节数。在系统之间进行数据传输的时候，小整数有价值的bit不多，如果按照计算机标准字节传送，则会造成传输资源的浪费。以整数1为例，占用4个字节，而有价值的bit是最低位的一个bit，其他值为0的bit传输到目标系统都是无价值的。为了实现小整数高效编码，Varint编码被提出。

1.4.1　编码规则

每个字节最高位表示编码是否继续，如果最高位为1，表示接下来的字节仍然是该数字的一部分；如果最高位为0，表示编码结束。每个字节里的其余7位表示数据值，采用低位字节补齐到高位的办法（Little-Endian方式）。

· 编码规则

1）整数先和0x10取与，判断右移7位后数值是否大于0。

2）取整数最低7位，如果步骤1）结果大于0，在最高位补1，否则在最高位补0，和最低7位凑成1个字节。

3）整数执行右移7位。

· 编码实现

上述编码规则对应的算法实现如下。

1.4.2　Varint编码示例

整数1的Varint编码如表1-10所示。

表1-10　整数1的Varint编码过程

整数-1的Varint编码如表1-11所示。

表1-11　整数-1的Varint编码过程

从上述编码过程可以看出，对于较小正整数，使用Varint编码可以减少字节数；对于较大正整数（如01111111，11111111，11111111，11111111），经过编码规则处理后，需要5个字节来表示；对于负整数，因其原码最高位为1，经过编码规则处理后，也需要5个字节来表示。

1.4.3　Varint编码的不足

从统计学角度看，大多数情况下人们使用的整数都是小正整数，通过Varint编码可以使用更少的字节来表示；但对于大正整数和负整数，Varint编码需要的字节数超过了标准语言定义的字节数。这也是Varint编码的不足之处。为了提高负整数的编码效率，ZigZag被提出，再结合Varint编码，使得编码效果达到最佳。