一文搞懂 ZigZag 算法及 Go 语言的实现

miaogaolin · · 486 次点击 · · 开始浏览    

> 收录于[《深入微服务》](https://mp.weixin.qq.com/mp/appmsgalbum?__biz=MzIzNzQwNTQwNg==&action=getalbum&album_id=2126863251039633410&scene=173&from_msgid=2247484609&from_itemidx=1&count=3&nolastread=1#wechat_redirect),作者 “老苗” 我原本是想研究 Protobuf 原理呢,但在研究过程中发现 Protobuf 在对负数编码时使用到了 ZigZag 算法,所以才有了本篇。当然你不懂 Protobuf 也完全不影响阅读。 在聊这个算法之前,我们先聊聊进制、补码相关的东西。如果你懂,那就指向往下翻。 该篇代码: [https://github.com/miaogaolin/gofirst/tree/main/zigzag](https://github.com/miaogaolin/gofirst/tree/main/zigzag) ## 进制 所谓进制,就是当某一位上的信息满时,需要往前进位。比如,十进制,就是当某一位上的数满十时进位;而某一位上的数满二时进位就是二进制,等等。 进位之间都可以相互转化,例如: 十进制:10 → 二进制:1010 → 十六进制:A 我之前看过一个答案,说:为什么十进制比较通用? 因为咱人类只有 10 个手指头,数一遍刚好十个数,所以十进制自然就成为默认的进制。那如果人类长 11 手指头,说不定就是十一进制。 后来计算机的出现,一个数据的有无是最天然的信息承载单元,所以由 0 和 1 组成的二进制很自然成为计算机的进制方式。在此基础上,为了方便信息的使用,又采用了八进制、十六进制。 好了,进制这个东西就聊到这了。 ## 三个东西 下来我们对一个十进制正整数表示为二进制,例如:十进制 10 等于二进制 1010。 那如果二进制表示一个负数,该怎么办?下来我们聊聊。 在计算机的世界里,定义了原码、反码和补码这几个东西。为了下来讲解简单点,我们假设使用一个字节(1Byte=8bits)表示一个数。 ### 1. 原码 我们用第一个位表示符号( 0 为非负数,1 为负数),剩下的位表示值。例如: - +8 → 原:00001000 - -8 → 原: 10001000 ### 2. 反码 我们用第一位表示符号( 0 为非负数,1 为负数),剩下的位,非负数保持不变,负数按位求反。例如: - +8 → 原:0000 1000 → 反:0000 1000 - -8 → 原:1000 1000 → 反:1111 0111 如果我们用原码或者补码来表示整数的二进制,有什么问题吗?表面上看,似乎挺好的。不过仔细思考就会发现两个问题: **第一**,0 居然可以用两个编码表示,+0 和 -0。 - 原:0000 0000 → 1000 0000 - 反:0000 0000 → 1111 1111 **第二**,计算机不知道符号位的存在,因此参加运算后,会出现一个奇怪的现象。 - 原码 1 + (-1) → 0000 0001 + 1000 0001 → 1000 0010 → -2 明显是不对的! - 反码 1 + (-1) → 0000 0001 + 1111 111 → 1111 1111 → -0 这看起来也怪怪的。 因此,为了解决这些问题,我们在计算机体系中引入了补码。 ### 3. 补码 我们用第一位表示符号( 0 为非负数,1 为负数),剩下的位非负数保持不变,负数按位求反末位加一。 - +8 → 原:0000 1000 → 补:0000 1000 - -8 → 原:1000 1000 → 补:1111 1000 现在我们看看,把符号带进去运算会出现什么结果? 1 + (-1) → 0000 0001 + 1111 1111 → 0000 0000 → 0 很明显,通过这样的方式,计算机进行运算的时候,就不用关心符号这个问题,统一都按照满 2 进 1 规则处理。 好了,进制和补码的知识就说到这了,下来进入真正的主题。 ## ZigZag 在大多数情况下,我们使用到的整数往往会比较小。 而我们为了在系统通讯时便于传输,往往需要一个整形(int32、int64)作为基本的传输类型。 因此在大多数系统中,以 4 Bytes 和 8 Bytes 来表示。这样,为了传输一个整型 1,我们需要传输 “00000000 00000000 00000000 00000001” 32 个 bits,而有价值的数据只有 1 位,剩下的都是浪费呀! 那怎么办呢?ZigZag 应用而生。那这个算法具体的思想是怎么样的呢? 对于正整数来讲,如果在传输数据时,我们把多余的 0 去掉,或者尽可能的减少无意义的 0。那么我们是不是就可以将数据进行压缩?那怎样进行压缩? 答案也很简单,例如 00000000 00000000 00000000 00000001 这个数。如果我们只发送 1 位 或者 1 字节 00000001,是不是就会很大程度减少无用的数据? 当然,如果这个世界上只有正整数,那我们就可以方便的做到这一点。可惜,他居然存在负数!那负数如何表示? 例如,十进制 -1 的补码表示为 11111111 11111111 11111111 11111111。 可以看到,前面全是 1,你说怎么弄? ZigZag 给出了一个很巧妙的方法。我们之前讲补码说过,补码的第一位是符号位,他阻碍了我们对于前导 0 的压缩,那么,我们就把这个符号位放到补码的最后,其他位整体前移一位。 补:**`1`**1111111 11111111 11111111 11111111 → 符号后移:11111111 11111111 11111111 111111**`1`** 但是即使这样,也是很难压缩的。于是,这个算法就把负数的所有数据位按位求反,符号位保持不变,得到了这样的整数,如下: 十进制:-1 → 补:**`1`**1111111 11111111 11111111 11111111 → 符号后移:11111111 11111111 11111111 1111111**`1`** → ZigZag:00000000 00000000 00000000 0000000**`1`** 而对于非负整数,同样的将符号位移动到最后,其他位往前挪一位,数据保持不变,如下: 十进制:1 → 补:**`0`**0000000 00000000 00000000 00000001 → 符号后移:00000000 00000000 00000000 0000001**`0`** → ZigZag:00000000 00000000 00000000 0000001**`0`** 这样一弄,正数、0、负数都有同样的表示方法了。我们就可以对小整数进行压缩了,对吧~ 于是,就可以写成如下的代码: ```go func int32ToZigZag(n int32) int32 { return (n << 1) ^ (n >> 31) } ``` `n << 1` 将整个值左移一位,不管正数、0、负数他们的最后一位都会变成了 0。讲解如下: 十进制:1 → 补:**`0`**0000000 00000000 00000000 00000001 → 左移一位:00000000 00000000 00000000 00000010 十进制:-1 → 补:**`1`**1111111 11111111 11111111 11111111 → 左移一位:11111111 11111111 11111111 11111110 `n >> 31` 将符号位放到最后一位。如果是非负数,则为全 0;如果是负数,就是全 1。讲解如下: 十进制:1 → 补:**`0`**0000000 00000000 00000000 00000001 → 右移 31 位:00000000 00000000 00000000 0000000**`0`** 十进制:-1 → 补:**`1`**1111111 11111111 11111111 11111111 → 右移 31 位:11111111 11111111 11111111 1111111**`1`** 最后这一步很巧妙,将两者进行按位异或操作。 十进制:1 → `n << 1` :00000000 00000000 00000000 00000010 ^ `n >> 31`: 00000000 00000000 00000000 0000000**`0`** → 00000000 00000000 00000000 0000001**`0`** 可以看到最终结果,数据位保持不变,而符号位也保持不变,只是符号位移动到了最后一位。 十进制:-1 → `n << 1`:11111111 11111111 11111111 11111110 ^ `n >> 31`:11111111 11111111 11111111 1111111**`1`** → 00000000 00000000 00000000 0000000**`1`** 可以看到,数据位全部反转了,而符号位保持不变,且移动到了最后一位。这一步真的写的很巧妙! ZigZag 还原代码如下: ```go func toInt32(zz int32) int32 { return int32(uint32(zz)>>1) ^ -(zz & 1) } ``` 类似的,我们还原的代码就反过来写就可以了。不过这里要注意一点,就是右移的时候,需要用不带符号的移动,否则如果第一位是 1 的时,移动时会补1。所以,使用了无符号的移位操作`uint32(zz)>>1`。 好了,有了该算法,就可以得到一个有前导 0 的整数。只是,该数据依然使用 4 字节存储。下来我们要考虑如何尽可能的减少字节数,并且还能还原。 例如,我们将 1 按照如上算法转化得到:00000000 00000000 00000000 00000010。 下来我们最好只需要发送 2 bits(10),或者发送 8 bits(00000010),把前面的 0 全部省掉。因为数据传输是以字节为单位,所以,我们最好保持 8 bits这样的单位。所以我们有 2 种做法: - 我们可以额外增加一个字节,用来表示接下来有效的字节长度,比如:00000001 00000010,前 8 位表示接下来有 1 个字节需要传输,第二个 8 位表示真正的数据。这种方式虽然能达到我们想要的效果,但是莫名的增加一个字节的额外浪费。有没有不浪费的办法呢? - 字节自表示方法。ZigZag 引入了一个方法,就是用字节自己表示自己。具体怎么做呢?我们来看看代码。 ```go func compress(zz int32) []byte { var res []byte size := binary.Size(zz) for i := 0; i < size; i++ { if (zz & ^0x7F) != 0 { res = append(res, byte(0x80|(zz&0x7F))) zz = int32(uint32(zz) >> 7) } else { res = append(res, byte(zz&0x7F)) break } } return res } ``` 大家先看看代码里那个 ^0x7F,他究竟是个什么数呢? - ^0x7F:11111111 11111111 11111111 10000000 他就是从倒数第八位开始,高位全为 1 的数。他的作用就是去除最后七位后,判断还有没有信息。 我们把 ZigZag 值传递给这个函数,这个函数就将这个值从低位到高位切分成每 7 bits 一组,如果高位还有有效信息,则给这 7 bits 补上 1 个 bit 的 1(0x80)。如此反复 直到全是前导 0,便结束算法。 举个例来讲: 十进制:-1000 → 补:**`1`**1111111 11111111 11111100 00011000 → ZigZag:00000000 00000000 00000111 1100111**`1`** 我们先按照七位一组的方式将上面的数字划开,0000 0000000 0000000 0001111 1001111。 详细步骤如下: 1. 他跟 ^0x7F 做与操作的结果,高位还有信息,所以,我们把低 7 位取出来,并在倒数第八位上补一个 1(0x80):11001111。 2. 将这个数右移七位,0000 0000000 0000000 0000000 0001111。 3. 再取出最后的七位,跟 ^0x7F 做与操作,发现高位已经没有信息了(全是0),那么我们就将最后 8 位完整的取出来:00001111,并且跳出循环,终止算法。 4. 最终,我们就得到了两个字节的数据 [11001111, 00001111]。 通过上面几步,我们就将一个 4 字节的 ZigZag 变换后的数字变成了一个 2 字节的数据。如果我们是网络传输的话,就直接发送这 2 个字节给对方进程。对方进程收到数据后,就可以进行数据的组装还原了。具体的还原操作如下: ```go func decompress(zzByte []byte) int32 { var res int32 for i, offset := 0, 0; i < len(zzByte); i, offset = i+1, offset+7 { b := zzByte[i] if (b & 0x80) == 0x80 { res |= int32(b&0x7F) << offset } else { res |= int32(b) << offset break } } return res } ``` 整个过程就和压缩的时候是逆向的,对于每一个字节,先看最高一位是否有 1(0x80)。如果有,就说明不是最后一个数据字节包,那取这个字节的最后七位进行拼装。否则,说明就是已经到了最后一个字节了,那直接拼装后,跳出循环,算法结束。最终得到 4 字节的整数。 ## 结语 算法不是很复杂,遇到哪块不懂了,就好好观察想想,这也是对 Protobuf 原理理解的重要部分。如果有不懂的,就在下方给我留言! 完整代码: [https://github.com/miaogaolin/gofirst/tree/main/zigzag](https://github.com/miaogaolin/gofirst/tree/main/zigzag)

有疑问加站长微信联系(非本文作者))

入群交流(和以上内容无关):加入Go大咖交流群,或添加微信:liuxiaoyan-s 备注:入群;或加QQ群:701969077

486 次点击  ∙  2 赞  
加入收藏 微博
暂无回复
添加一条新回复 (您需要 登录 后才能回复 没有账号 ?)
  • 请尽量让自己的回复能够对别人有帮助
  • 支持 Markdown 格式, **粗体**、~~删除线~~、`单行代码`
  • 支持 @ 本站用户;支持表情(输入 : 提示),见 Emoji cheat sheet
  • 图片支持拖拽、截图粘贴等方式上传