学习Protobuf，ZigZag是啥你真的知道么？
结合上一篇文章，我们了解到通过Varint 编码整数，如遇到负数或大整数，就不具备压缩优势了？由于引入了MSB，不但没有好的压缩效果，还加大了存储，这明显不是我们想要的。以下，我们聊聊怎么解决这类问题。
这篇文章，也是学习Protobuf过程中偶然所得，算法简洁，篇幅较短，预计阅读时间 8 分钟，如果对您有帮助，还望不吝评价，求点赞、求评论、求转发。
在聊ZigZag算法之前，我们先聊聊进制、原码、反码、补码相关的知识点，如果你懂，可跳过直接往下翻。
什么是进制？
所谓进制，就是当某一位上的信息满时，需要往前进位。比如，十进制，就是当某一位上的数满十时进位；而某一位上的数满二时进位就是二进制，等等。
进位之间都可以相互转化，例如：十进制：10 → 二进制：1010 → 十六进制：A
我之前看过一个答案，说：为什么十进制比较通用？因为咱人类只有 10 个手指头，数一遍刚好十个数，所以十进制自然就成为默认的进制。那如果人类长 11 手指头，说不定就是十一进制。
后来计算机的出现，一个数据的有无是最天然的信息承载单元，所以由 0 和 1 组成的二进制很自然成为计算机的进制方式。—— 老苗
计算机系统里面对二进制定义了原码、反码、补码，为了更简单的理解，后续我们用1 Byte=8 bits进行讲解。
原码是啥？
定义：用第一位表示符号(0为非负，1为负数)，其余位表示值，如下：
-
+8 -> 原码：0000 1000 -
-8 -> 原码：1000 1000
有了原码的表示方法就可以对数进行算法运算，但是很快就发现用带符号位的原码进行乘除运算结果正确，但在加减运算时就出现了问题，如下：
乘法规则：符号位做“异或”运算，数值位做类似十进制的“乘法”运算
十进制：+8 * (-8) = -64
原码：0000 1000 * 1000 1000 = 1100 0000 = -64
十进制：+8 + (-8) = 0
原码：0000 1000 + 1000 1000 = 1001 0000 = -16 # 显然不正确
看起来加法运算也没什么问题，发现问题是出在符号位上？于是计算机大佬们引入了反码。
反码都做了啥？
定义：用第一位表示符号(0为非负，1为负数)，其余位，非负数保持不变，负数按位求反，如下：
-
+8 -> 原码：0000 1000 -> 反码：0000 1000 -
-8 -> 原码：1000 1000 -> 反码：1111 0111
我们继续进行上述的加法运算
-
十进制：+8 + (-8) = 0 -
反码：0000 1000 + 1111 0111 = 1111 1111 = -0
竟然结果是-0，这个结果让人猝不及防啊！！！
分析发现，如果用原码 + 补码表示二进制计算，表面上看，似乎挺好的。不过仔细思考就会发现两个问题：
第一，0竟然可以用两种编码表示，+0 和 -0：
-
+0 -> 原码：0000 0000 -> 反码：0000 0000 -
-0 -> 原码：1000 0000 -> 反码：1111 1111
第二，计算机不清楚符号位的存在，因此参加运算后，会出现结果为-0这样的现象。
这看起来怪怪的，为了解决这些问题，计算机巨佬们又引入了补码
补码有啥用？
定义：用第一位表示符号(0为非负，1为负数)，剩下的位非负数保持不变，负数按位求反且末尾加一。
-
+8 -> 原码：0000 1000 -> 补码：0000 1000 -
-8 -> 原码：1000 1000 -> 补码：1111 1000
现在我们继续看看，把符号位带入运算会出现什么结果？
-> 8 + (-8)
-> 0000 1000 + 1111 1000
-> 0000 0000
-> 0
很明显，通过引入补码，我们解决了此类问题，计算机运算过程中，就不用关心符号问题，统一按照满二进一规则处理即可
好了，知识小点就说到这了，接下来，进入真正的主题。
ZigZag 是什么？
在大多数计算机系统中，我们通常使用定长整型(fixed length intergers)表示数值。比如：
-
用 4 bytes表示Int32 -
用 8 bytes表示Int64
为什么这样设置呢？这样能便于我们的计算机处理，加快处理的速度。
但是在系统网络通信(RPC)时，为了传输一个1，我们需要传输00000000 00000000 00000000 00000001 32 个 bits。这么多字符，而有价值的数据只有 1 位，这T&M也太浪费了呀！
那该怎么办呢？ZigZag算法由此而生。
ZigZag 的原理
编码介绍
ZigZag编码将有符号整数映射成无符号整数，以便绝对值较小的数字对应较小的编码值，比如：-1 -> 1，1 -> 2，具体如图：
| 原数 | 编码 |
|---|---|
| 0 | 0 |
| -1 | 1 |
| 1 | 2 |
| -2 | 3 |
| 2 | 4 |
| ... | ... |
| -(2^31 -1) | 2^32 - 3 |
| 2^31 -1 | 2^32 -2 |
如上，这种方式通常由正整数和负整数来回曲折编码，看着还挺有意思的。难道就因为这样，计算机大佬们才给取了个名字叫ZigZag(锯齿形线条)算法？？？
编码规则
-
a.非负整数，符号位后移 -
b.负整数，符号位后移，数据位按位求反
在大多数计算机系统中，以4 Bytes和8 Bytes 来表示整数(Int32、Int64)。下面我们选择Int32进行一个简单的演示，如下：
-
十进制：0
-
补 码 ： 00000000 00000000 00000000 00000000
-
ZigZag：00000000 00000000 00000000 0000000 0 -
十进制：1
-
补 码 ： 00000000 00000000 00000000 00000001
-
ZigZag：00000000 00000000 00000000 0000001 0 -
十进制：-1
-
补 码 ： 11111111 11111111 11111111 11111111
-
ZigZag：00000000 00000000 00000000 0000000 1
解码规则
-
类似编码，反向操作即可
ZigZag 编码实现(Python)
def int32_to_zigzag(n):
return (n << 1) ^ (n >> 31)
ZigZag 解码实现(Python)
def zigzag_to_int32(zz):
return (zz >> 1) ^ -(zz & 1)
总结一下
大多数情况下，通过ZigZag编码结合Varint算法，对整数都有好的压缩效果，但如果遇到绝对值大的整数，就不再具有压缩优势了。
不过，我们通常使用到的整数往往也都比较小。
参考文档
-
https://en.wikipedia.org/wiki/Zigzag -
https://developers.google.com/protocol-buffers/docs/encoding#types -
https://studygolang.com/articles/35309
❤️❤️❤️读者每一份热爱都是笔者前进的动力！我是三十一，感谢各位朋友：求点赞、求评论、求转发，大家下期见！