varint编码实现原理

简言

1. varint即 variable int，也就是变长整型，在mysql，levelDB，protobuf中都有使用

2. varint编码的优点是对数值较小的数进行编码后占用字节较少，比如[0-127]只占用1个字节，[128~16383]只占用2个字节。而我们常用的int32,int64之类，无论数字多大，都固定占4字节，8字节

3. varint编码的缺点是对数值较大的数和负数进行编码后占用字节较多，最多可能要占10个字节（表示负数的时候）

4. 因为生活中真实用到的数字往往都不大且是正数，所以综合优点缺点varint还是能节省一些空间

编码原理

varint 对数字的二进制，从右往左，每7位分割成一块

如果不是最后一块，则左边补1，组成一个字节

如果是最后一块，则左边补0，组成1个字节

最终保存的时候，根据分割块的顺序依次从左往右填

举例(为了方便大家看，从右往左，每7位一个颜色)

举例1：

数字5，二进制101，从右往左依次取7位

第一次取7位，由于只有3位，所以只分割出来1块，也就是最后一块，根据规则前面补0，得到00000101

所以，varint表示法是00000101

跟原来二进制一样，所以[0~255]之间的数字只占用1个字节

举例2：

数字130，二进制10000010，从右往左依次取7位

第一次取出来的0000010，因为前面还有数字1，自己不是最后一块，根据规则左边补1，得到 10000010

第二次取出来的1，因为前面已经没数字了，这里是最后一块了，根据规则前面补0，得到00000001

把这些分割后新组成的块，从左往右填

所以，varint表示法是10000010   00000001

举例3：

数字12345678，二进制101111000110000101001110，从右往左依次取7位

第一次取出来的1001110，因为自己不是最后一块，根据规则左边补1，得到11001110

第二次取出来的1000010，因为自己不是最后一块，根据规则左边补1，得到11000010

第三次取出来的1110001，因为自己不是最后一块，根据规则左边补1，得到11110001

第四次取出来的101，因为自己是最后一块，根据规则左边补0，得到00000101

把这些分割后新组成的块，从左往右填

所以，最终varint表示法是11001110  11000010  11110001   00000101