varint和zigzag编码

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

原码、反码、补码

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

然后回顾下:

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

详解

编码

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

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

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

varint编码java代码表示:

1
2
3
4
5
6
7
8
9
10
11
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,继续读下一个字节,否则跳出循环。

1
2
3
4
5
6
7
8
9
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也是类似的处理方式。