本来想研究一下Protobuf的原理，但是在研究的过程中发现Protobuf在对负数进行编码时使用了ZigZag算法，于是就有了这篇文章。当然，如果你不懂Protobuf，完全不影响阅读。在说这个算法之前，先说说base和complement相关的东西。如果您明白，请指向向下滚动。代码：https://github.com/miaogaolin/gofirst/tree/main/zigzag所谓basesystem，就是当某个bit上的信息满了，需要往前走。例如，十进制表示当某位数字满十时，当某位数字满二时进位进位，等等。进位可以相互转换，例如：十进制：10→二进制：1010→十六进制：A之前看过一个回答，说：为什么十进制更常见？因为我们人类只有10根手指，而数的数恰好是10，所以十进制自然成为了默认的基数系统。那么如果人类有11根手指，说不定就是十进制。后来随着计算机的出现，一个数据的有无就是最自然的信息承载单位，所以0和1组成的二进制自然而然成为了计算机的基本系统。在此基础上，为了方便信息的使用，采用了八进制和十六进制。好了，系统说到这里。三件事下来，我们把一个十进制的正整数表示成二进制，比如：十进制的10等于二进制的1010。那如果二进制表示一个负数呢？下来我们谈谈吧。在计算机世界中，定义了原码、反码和补码。为了简单说明，我们假设用一个字节（1Byte=8bits）来表示一个数。1、原代码中，我们用第一位表示符号（0为非负数，1为负数），其余位表示数值。例如：+8→original:00001000-8→original:100010002在反码中，我们用第一位表示符号（0为非负数，1为负数），其余位，非负数不变，负数按位相反计算。例如：+8→original:00001000→inverse:00001000-8→original:10001000→inverse:11110111如果用原码或者补码来表示整数的二进制，有没有问题？从表面上看，似乎还可以。但是仔细想想，你会发现两个问题：第一，0可以用+0和-0两种编码来表示。Original:00000000→10000000Reverse:00000000→11111111二、计算机不知道符号位的存在，所以参与运算后，会出现一个奇怪的现象。原码1+(-1)→00000001+10000001→10000010→-2显然是错误的！反码1+(-1)→00000001+1111111→11111111→-0这看起来也很奇怪。因此，为了解决这些问题，我们在计算机系统中引入了补码。3、补码中，我们用第一位表示符号（0为非负数，1为负数），非负数的其余位不变，负数为按位取反，最后一位加一。+8→原:00001000→补:00001000-8→原:10001000→补:11111000现在让我们看看，把符号带进去会是什么运算结果呢？1+(-1)→00000001+11111111→00000000→0很明显，这样计算机在进行计算的时候，不需要关心符号的问题，按照规则统一处理满2变成1。好了，底和补的知识就说完了，下面进入正题。ZigZag在大多数情况下，我们使用的整数往往相对较小。为了在系统通信时方便传输，我们往往需要一个整数（int32，int64）作为基本传输类型。因此，在大多数系统中，用4Bytes和8Bytes来表示。这样，为了传输一个整数1，我们需要传输“00000000000000000000000000000001”32位，而有价值的数据只有1位，剩下的都浪费了！那我们该怎么办呢？ZigZag应用程序诞生了。那么这个算法的具体思路是什么呢？对于正整数，如果我们在传输数据时去掉多余的0，或者尽量减少无意义的0。那么我们可以压缩数据吗？那么如何压缩呢？答案也很简单，比如数字00000000000000000000000000000001。如果我们只发送1位或者1字节00000001，是不是会大大减少无用数据呢？当然，如果这个世界上只有正整数，那我们这样做也很方便。可惜，他居然是负数！如何表示负数？比如-1十进制的补码表示为11111111111111111111111111111111可以看到，前面全是1。你怎么做呢？ZigZag给出了一个非常巧妙的方法。前面讲补码的时候说了，补码的第一位是符号位，不让我们压缩前导0，所以我们把这个符号位放在补码的末尾，其他的比特整体向前移动。补：**1**1111111111111111111111111111111→符号后移：111111111111111111111111111111**1**但即便如此，也很难压缩。因此，本算法将负数的所有数据位逐位取反，符号位不变，得到整数如下：十进制：-1→补数：**1**1111111111111111111111111111111→Signbackward:1111111111111111111111111111111**1**→ZigZag:0000000000000000000000000000000**1**对于非负整数，符号位也移到末尾，其他位向前移，并且数据保持不变。如下：十进制：1→补数：**0**0000000000000000000000000000001→向后符号：0000000000000000000000000000001**0**→ZigZag：000000000**00**0有0和负数相同的表示。我们可以压缩小整数对吧~所以，我们可以写下面的代码：左，不管正数、0、负数，最后一位都变成0。解释如下：十进制：1→补数：**0**0000000000000000000000000000001→左一位：00000000000000000000000000000010十进制:-1→补码：**1**11111111111111左1一位：1111111111111111111111111111111111111111111111110n>>31把符号位放到最后一位。如果是非负数，则全为0；如果为负，则全为1。解释如下：Twita:1→supplement:**0**000000000000000000000001→Shit31-bit:000000000000000000000000000000**0**TimSystem:-1→Supplement:**1**1111111111111111111→Shiftright→bits:1111111111111111111111111111111**1**最后一步很巧妙，对两者进行按位异或运算。Top:1→n<<1:0000000000000000000000001010^n>>31:000000000000000000000000000000000**0**→000000000000000000000001**0**数据位保持不变，数据位可以看到最终的结果位不变，符号位也保持不变，只是符号位移到了最后一位。TopSystem:-1→N<<1:11111111111111111111111111111110^n>>31:1111111111111111111111111111**1**→000000000000000000000**1**可以看到。符号位保持不变并移动到最后一位。这一步真的写得很巧妙！之字折线恢复代码如下：functoInt32(zzint32)int32{returnint32(uint32(zz)>>1)^-(zz&1)}同理，我们可以反过来写恢复代码。不过这里要注意一点，向右移动的时候需要使用无符号移动，否则如果第一位是1，移动的时候会加1。因此，使用了无符号移位操作uint32(zz)>>1。那么，使用这个算法，您可以获得一个前导0的整数。但是，数据仍然使用4个字节进行存储。接下来，我们要考虑如何尽可能减少字节数并恢复它。比如我们把1按照上面的算法进行转换得到：00000000000000000000000000000010接下来我们最好只发送2位（10），或者发送8位（00000010），前面的0全部省略。由于数据传输以字节为单位，我们最好保持8位这样的单位。所以我们有两种方法：我们可以增加一个额外的字节来表示下一个有效字节长度，例如：0000000100000010，前8位表示接下来有1个字节要传输，后8位表示真正的数据。这种方法虽然可以达到我们想要的效果，但是莫名其妙的多了一个字节的浪费。有没有办法不浪费呢？字节自表示法。ZigZag引入了一种以字节表示自身的方法。怎么做？让我们看一下代码。funccompress(zzint32)[]byte{varres[]bytesize:=binary.Size(zz)fori:=0;i
