zig-zag编码和group varint编码

zig-zag编码

zig-zag编码是一种将有符整形转化成无符的整形的一种方式。比如int32转uint32:(n<<1)^(n>>31)

刚开始这个代码看了好久都没看懂，后来终于明白了。其实zig-zag的原理就是，将int的0,-1,1,-2,2,-3,3...对应的转换成uint的0,1,2,3,4,5,6...

找一找规律，其实转化方式就是：对正数，将它乘以2；对负数，将它的数值乘2减1

乘以2用位运算就是(n>>1)，而补码做加法减法都是一样的，所以这里正好是加上符号位！于是最终就是公式(n<<1)^(n>>31)。

即使明白了zig-zag做变换的本质，那么转回来也很容易明白了。可以看到规律：偶数都对应转换前的负数，奇数都对应转换前的正数。比如2是-1转换得到的，3是2转换得到的。

转换回去就是将数值部分除以2，用奇偶决定符号位。(n >> 1) ^ -(int32_t)(n & 1)

思考，我看到zig-zag的使用场景之一是，做变长整形压缩。先将int用zig-zag转成uint，再用变长编码做uint的压缩。

我在想一个问题是这样值不值？因为用zig-zag编码之后，对于原来的正数它的值就增大了两倍，需要更长的变长编码，压缩率变低了。考虑一种极端的情景就是126,126,122,124,123,111,111,103,125,127,125,-1,3,111...这样一个序列，绝大部分都是正数，如果不进行zig-zag直接做变长编码，只要13＋5个字节就可以编码下来了。但如果先做zig-zag，就需要13*2+1个字节才能压缩，亏了！

最后要想一下什么时候做是划算的。对负数，不做zig-zag需要5个字节编码，做了需要1-4个字节。对正数，不做zig-zag需要原来字节数的两倍。假设平均下来每个数的变长编码字节长度为E，负数在整个序列中占的比重是p，对于最终编码长度的期望，给套公式就是： non-zig-zag = 5p+E(1-p) = 5p+E-Ep zig-zag = Ep+E2*(1-p) = 2E-Ep

最终就是比较E跟5p的大小决定变长编码之前做zig-zag编码是否划算。如果E小于5p，则做zig-zag是划算的。E小于5p的含义就是按数值部分的变长编码平均字节长度，要小于负数比例的5倍。

group varint编码

group varint编码与varint编码不同。varint编码中用1位来决定下一字节是否还是属于同一个int。而group varint编码的出发点是，用2个位来记录长度。将4个int为一组进行编码，长度信息全部记录在第一个字节中。

由于这种方式能大大地减少分支，移位，取mask的操作，因此这种编码算法的速度非常快。