varint和zigzag编码

对于二进制编码，经常需要对数据进行压缩以节省空间，varint可以压缩较小的正数，但是对于负数varint反而更浪费空间，zigzag编码可以处理负数，使负数也可以使用varint编码压缩，protobuf和thrift都使用二者结合的方式来压缩数字类型。

原码、反码、补码

首先，计算机为了方便位运算，使用补码来存储数字。

然后回顾下：

• 原码：最高位为符号位，剩余位表示绝对值；
• 反码：除符号位外，对原码剩余位依次取反；
• 补码：对于正数，补码为其自身；对于负数，除符号位外对原码剩余位依次取反然后+1。

详解

编码

本文以int类型为例，详细介绍如果通过varint+zigzag编码技术压缩数字。

首先，我们常用的数字其实多数都不是很大，比如：商品的价值、动态计数等，对于这些不是很大的数字，二进制的高位多数是0。

varint编码每个字节前1位表示下一个字节是否也是该数字的一部分，后7位表示实际的值，最后，先低位后高位，对于int类型来说，varint编码最少占用1个字节，最多占用5个字节。

varint编码java代码表示：

byte[] bytes = new byte[5];
int idx = 0;
while (true) {
  if ((n & ~0x7F) == 0) { // 除低7位，全部为0
    bytes[idx++] = (byte) n;
    break;
  } else { // 除低7位，不全部为0
    bytes[idx++] = ((byte) ((n & 0x7F) | 0x80)); // 高1位置1，低7位按位与得到实际值
    n >>>= 7;
  }
}

varint

例如，对于int类型1来说，二进制表示为00000000 00000000 00000000 00000001，总共占用4个字节，然而，前3个字节都是0，varint就是通过压缩高位的0来达到节省空间的目的，使用varint压缩后，二进制表示为00000010，只占用1个字节。

对于int类型2^30来说二进制表示为01000000 00000000 00000000 00000000，使用varint压缩后，二进制表示为00000001 00000001 00000001 00000001 00001000，占用5个字节。

zigzag

对于负数来说，因为最高位符号位始终为1，使用varint编码就很浪费空间，zigzag编码就是解决负数的问题的，同时其对正数也没有很大的影响。

int类型zigzag变换的代码表示为(n << 1) ^ (n >> 31)

• 左移1位可以消去符号位，低位补0
• 有符号右移31位将符号位移动到最低位，负数高位补1，正数高位补0
• 按位异或
  • 对于正数来说，最低位符号位为0，其他位不变
  • 对于负数，最低位符号位为1，其他位按位取反

-1的二进制表示为11111111 11111111 11111111 11111111，zigzag变换后00000000 00000000 00000000 00000001，再用varint编码，是不是很小了。

1的二进制表示为00000000 00000000 00000000 00000001，zigzag变换后00000000 00000000 00000000 00000010，再用varint编码，依然很小。

编码步骤：

• zigzag
• varint

解码

解码步骤和编码步骤相反，先读取varint，再执行zigzag解码

varint

一个一个字节读入，判断高位是否为1，如果是1，继续读下一个字节，否则跳出循环。

int result = 0;
int shift = 0;
while (true) {
  byte b = readByte();
  result |= (int) (b & 0x7f) << shift;
  if ((b & 0x80) != 0x80)
    break;
  shift += 7;
}

zigzag

zigzag操作为(n >>> 1) ^ -(n & 1)

• 无符号右移1位
• 按位与1，然后取负值，这一步非常巧妙，对于正数就是0，负数就是-1
• 按位异或得到结果
  • 正数是与0按位异或
  • 负数是与-1按位异或

总结

varint+zigzag编码对于越接近0的数，压缩越好，所以可以在一些常用的情况下压缩数字类型。

对于short、long、double也是类似的处理方式。