What is zigzag

[lyj289]

Google的Protobuf中，在处理有符号整数时，使用了zigzag, 主要是对负数进行编码，使得负数也可以用较小的整数表示，从而在传输过程中可以通过一定算法进行压缩，减少传输量，提高传输效率。

比如 -1 用补码表示为111111111，如果是32位，为111111111 111111111 111111111 111111111，相比1 000000000 000000000 000000000 000000001, -1 则更难被压缩。

zigzag核心思想是，表示负数时，将符号为放在最右侧，将数据位取反，-1 可以表示为000000000 000000000 000000000 000000001, 1表示为000000000 000000000 000000000 000000010

然后在此基础上，再进行压缩，将前缀0去除，减少传输字节量。

zigzag的前提是，数据绝对值范围确实比较小，如果绝对值都很大，压缩效果不明显。

核心算法比较精简。

// Encode:
function encode32(num) {
  return (num << 1) ^ (num >> 31)
}

// Decode
function decode32(num) {
  return (num >>> 1) ^ -(num & 1)
}

另外， Echarts在处理GeoJSON时，也利用zigzag做了处理，压缩了文件大小

参考

• 小而巧的zigzag
• https://developers.google.com/protocol-buffers/docs/encoding
• https://github.com/chrisdickinson/zigzag/blob/master/index.js
• Echart encode