学习Protobuf，ZigZag是啥你真的知道么？

结合上一篇文章《学习Protobuf，Varint是啥你真的知道么？》，我们了解到通过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，具体如图：

如上，这种方式通常由正整数和负整数来回曲折编码，看着还挺有意思的。难道就因为这样，计算机大佬们才给取了个名字叫ZigZag(锯齿形线条)算法？？？

编码规则

• a.非负整数，符号位后移
• b.负整数，符号位后移，数据位按位求反

在大多数计算机系统中，以4 Bytes和8 Bytes 来表示整数(Int32、Int64)。下面我们选择Int32进行一个简单的演示，如下：

• 十进制：0
  • 补 码 ：00000000 00000000 00000000 00000000
  • ZigZag：00000000 00000000 00000000 00000000
• 十进制：1
  • 补 码 ：00000000 00000000 00000000 00000001
  • ZigZag：00000000 00000000 00000000 00000010
• 十进制：-1
  • 补 码 ：11111111 11111111 11111111 11111111
  • ZigZag：00000000 00000000 00000000 00000001

解码规则

• 类似编码，反向操作即可

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

❤️❤️❤️读者每一份热爱都是笔者前进的动力！我是三十一，感谢各位朋友：求点赞、求评论、求转发，大家下期见！