目的
了解zigzag算法的原理
前言
现代计算机一般是用4个字节（32bit）或者8个字节（64bit）为一个单位来表示一个字符，但是我们的数字大多数情况是比较小的，用不了这么多bit，在网络传输过程中会造成网络流量的浪费。比如1，用四个字节表示是00000000 00000000 00000000 00000001,32个bit，在网络中传输这么多的0造成浪费，这个时候我们只需要传1一个bit就可以了。
当然我们有一些算法对此进行了优化，比如把前面为0的bit去掉，到了目的地再补上就好了。但是如果是负数呢？比如-1,用四个字节表示是10000000 00000000 00000000 00000001,第一个符号位是1，不好去掉。
zigzag算法就是解决负数这种情况的。
进制
在了解zigzag算法之前，我们先了解一下进制的概念。
所谓进制，就是当某一位上的信息满时，需要往前进位。比如，十进制，就是当某一位上的数满十时进位；而某一位上的数满二时进位就是二进制，等等。
进位之间都可以相互转化，例如：
十进制：10 → 二进制：1010 → 十六进制：A
我之前看过一个答案，说：为什么十进制比较通用？
因为咱人类只有 10 个手指头，数一遍刚好十个数，所以十进制自然就成为默认的进制。那如果人类长 11 手指头，说不定就是十一进制。
后来计算机的出现，一个数据的有无是最天然的信息承载单元，所以由 0 和 1 组成的二进制很自然成为计算机的进制方式。在此基础上，为了方便信息的使用，又采用了八进制、十六进制。
原码、反码、补码
原码
我们用第一个位表示符号（ 0 为非负数，1 为负数），剩下的位表示值。例如：
- +8 → 原码：00001000
- -8 → 原码: 10001000
反码
我们用第一位表示符号（ 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 110
→ 1111 1111
→ -0
这看起来也怪怪的。
因此，为了解决这些问题，我们在计算机体系中引入了补码。
补码
我们用第一位表示符号（ 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
补码：11111111 11111111 11111111 11111111
→ 符号后移：11111111 11111111 11111111 1111111
但是即使这样，也是很难压缩的。于是，这个算法就把负数的所有数据位按位求反，符号位保持不变，得到了这样的整数，如下：
十进制：-1
→ 补码：11111111 11111111 11111111 11111111
→ 符号后移：11111111 11111111 11111111 11111111
→ ZigZag：00000000 00000000 00000000 00000001
而对于非负整数，同样的将符号位移动到最后，其他位往前挪一位，数据保持不变，如下：
十进制：1
→ 补码：00000000 00000000 00000000 00000001
→ 符号后移：00000000 00000000 00000000 00000010
→ ZigZag：00000000 00000000 00000000 00000010
这样一弄，正数、0、负数都有同样的表示方法了。我们就可以对小整数进行压缩了，对吧~
于是，就可以写成如下的代码：
func int32ToZigZag(n int32) int32 {
return (n << 1) ^ (n >> 31)
}下面对这段代码做一个讲解
`n << 1` 将整个值左移一位，不管正数、0、负数他们的最后一位都会变成了 0。<br>
→ 补码：`0`**0000000 00000000 00000000 00000001**<br>
→ 左移一位：00000000 00000000 00000000 00000010<br>
`n >> 31` 将符号位放到最后一位。如果是非负数，则为全 0；如果是负数，就是全 1<br>
→ 补码：`0`**0000000 00000000 00000000 00000001**<br>
→ 右移 31 位：**00000000 00000000 00000000 0000000**`0`<br>
将两者进行按位异或操作<br>
→ `n << 1` ：**00000000 00000000 00000000 00000010**<br>
`n >> 31`： **00000000 00000000 00000000 0000000**`0`<br>
→ **00000000 00000000 00000000 0000001**`0`<br>
再把结果还原，最后一位为符号位，移动到第一位，由于符号位是0，表示正数，则数字为不变，得到<br>
`0`**00000000 00000000 00000000 0000001**，即1的补码。<br>
```对于十进制-1```<br>
`n << 1` 将整个值左移一位，不管正数、0、负数他们的最后一位都会变成了 0。<br>
→ 补码：`1`**1111111 11111111 11111111 11111111**<br>
→ 左移一位：**11111111 11111111 11111111 11111110**<br>
`n >> 31` 将符号位放到最后一位。如果是非负数，则为全 0；如果是负数，就是全 1<br>
→ 补码：`1`**1111111 11111111 11111111 11111111**<br>
→ 右移 31 位：**11111111 11111111 11111111 1111111**`1`<br>
将两者进行按位异或操作<br>
→ `n << 1`：**11111111 11111111 11111111 11111110**<br>
`n >> 31`：**11111111 11111111 11111111 1111111**`1`**<br>
→ 00000000 00000000 00000000 0000000**`1`<br>
再把结果还原，最后一位为符号位，移动到第一位，由于符号位是1，表示负数，则数字为取反，得到<br>
`1`**1111111 11111111 11111111 11111111**，即-1的补码。<br><br>
可以看到最终结果，数据位保持不变，而符号位也保持不变，只是符号位移动到了最后一位。
ZigZag 还原代码如下：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 引入了一个方法，就是用字节自己表示自己。具体怎么做呢？我们来看看代码。
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。
1. 将这个数右移七位，0000 0000000 0000000 0000000 0001111。
1. 再取出最后的七位，跟 ^0x7F 做与操作，发现高位已经没有信息了（全是0），那么我们就将最后 8 位完整的取出来：00001111，并且跳出循环，终止算法。
1. 最终，我们就得到了两个字节的数据 [11001111, 00001111]。
通过上面几步，我们就将一个 4 字节的 ZigZag 变换后的数字变成了一个 2 字节的数据。如果我们是网络传输的话，就直接发送这 2 个字节给对方进程。对方进程收到数据后，就可以进行数据的组装还原了。具体的还原操作如下：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 字节的整数。
# 总结
ZigZag算法比较简单，就是在补码的基础上将符号位移动到末尾，如果是负数，则数字位取反。这里主要用到了计算机的移位和取反操作很简单。取反就是：正数跟（00000000，也就是0的补码）做异或操作，负数跟（11111111，也就是-1的补码）做异或操作，统一成一个表达式就是(假设用四个字节32bit表示一个数字)：```(x<<1) ^ (x>>32)```，逆向操作是：```int32(uint32(x)>>1) ^ -(x & 1)```,这两个表达式不懂的自己多细细揣摩，在纸上多画画。
# 参考
[1][深入微服务：2. 研究 Protobuf 时发现一个挺好的算法 — ZigZag](https://printlove.cn/posts/ms/zigzag/)<br>
