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

2024-05-22 13:01:05 101

我原本是想研究Protobuf原理呢，但在研究过程中发现Protobuf在对负数编码时使用到了ZigZag算法，所以才有了本篇。当然你不懂Protobuf也完全不影响阅读。

在聊这个算法之前，我们先聊聊进制、补码相关的东西。如果你懂，那就指向往下翻。

进制

所谓进制，就是当某一位上的信息满时，需要往前进位。比如，十进制，就是当某一位上的数满十时进位；而某一位上的数满二时进位就是二进制，等等。

进位之间都可以相互转化，例如：

十进制：10→二进制：1010→十六进制：A

我之前看过一个答案，说：为什么十进制比较通用？

因为咱人类只有10个手指头，数一遍刚好十个数，所以十进制自然就成为默认的进制。那如果人类长11手指头，说不定就是十一进制。

后来计算机的出现，一个数据的有无是最天然的信息承载单元，所以由0和1组成的二进制很自然成为计算机的进制方式。在此基础上，为了方便信息的使用，又采用了八进制、十六进制。

好了，进制这个东西就聊到这了。

三个东西

下来我们对一个十进制正整数表示为二进制，例如：十进制10等于二进制1010。

那如果二进制表示一个负数，该怎么办？下来我们聊聊。

在计算机的世界里，定义了原码、反码和补码这几个东西。为了下来讲解简单点，我们假设使用一个字节（1Byte=8bits）表示一个数。

1.原码

我们用第一个位表示符号（0为非负数，1为负数），剩下的位表示值。例如：

+8→原：00001000
-8→原:10001000

2.反码

我们用第一位表示符号（0为非负数，1为负数），剩下的位，非负数保持不变，负数按位求反。例如：

+8→原：00001000→反：00001000
-8→原：10001000→反：11110111

如果我们用原码或者补码来表示整数的二进制，有什么问题吗？表面上看，似乎挺好的。不过仔细思考就会发现两个问题：

第一，0居然可以用两个编码表示，+0和-0。

原：00000000→10000000
反：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个bits，而有价值的数据只有1位，剩下的都是浪费呀！

那怎么办呢？ZigZag应用而生。那这个算法具体的思想是怎么样的呢？

对于正整数来讲，如果在传输数据时，我们把多余的0去掉，或者尽可能的减少无意义的0。那么我们是不是就可以将数据进行压缩？那怎样进行压缩？

答案也很简单，例如00000000000000000000000000000001这个数。如果我们只发送1位或者1字节00000001，是不是就会很大程度减少无用的数据？

当然，如果这个世界上只有正整数，那我们就可以方便的做到这一点。可惜，他居然存在负数！那负数如何表示？

例如，十进制-1的补码表示为11111111111111111111111111111111。

可以看到，前面全是1，你说怎么弄？

ZigZag给出了一个很巧妙的方法。我们之前讲补码说过，补码的第一位是符号位，他阻碍了我们对于前导0的压缩，那么，我们就把这个符号位放到补码的最后，其他位整体前移一位。

补：**1**1111111111111111111111111111111

→符号后移：111111111111111111111111111111**1**

但是即使这样，也是很难压缩的。于是，这个算法就把负数的所有数据位按位求反，符号位保持不变，得到了这样的整数，如下：

十进制：-1

→补：**1**1111111111111111111111111111111

→符号后移：1111111111111111111111111111111**1**

→ZigZag：0000000000000000000000000000000**1**

而对于非负整数，同样的将符号位移动到最后，其他位往前挪一位，数据保持不变，如下：

十进制：1

→补：**0**0000000000000000000000000000001

→符号后移：0000000000000000000000000000001**0**

→ZigZag：0000000000000000000000000000001**0**

这样一弄，正数、0、负数都有同样的表示方法了。我们就可以对小整数进行压缩了，对吧~

于是，就可以写成如下的代码：

funcint32ToZigZag(nint32)int32{

	return(n<<1)^(n>>31)

}

n<<1将整个值左移一位，不管正数、0、负数他们的最后一位都会变成了0。讲解如下：

十进制：1

→补：**0**0000000000000000000000000000001

→左移一位：00000000000000000000000000000010

十进制：-1

→补：**1**1111111111111111111111111111111

→左移一位：11111111111111111111111111111110

n>>31将符号位放到最后一位。如果是非负数，则为全0；如果是负数，就是全1。讲解如下：

十进制：1

→补：**0**0000000000000000000000000000001

→右移31位：0000000000000000000000000000000**0**

十进制：-1

→补：**1**1111111111111111111111111111111

→右移31位：1111111111111111111111111111111**1**

最后这一步很巧妙，将两者进行按位异或操作。

十进制：1

→n<<1：00000000000000000000000000000010^

n>>31：0000000000000000000000000000000**0**

→0000000000000000000000000000001**0**

可以看到最终结果，数据位保持不变，而符号位也保持不变，只是符号位移动到了最后一位。

十进制：-1

→n<<1：11111111111111111111111111111110^

n>>31：1111111111111111111111111111111**1**

→0000000000000000000000000000000**1**

可以看到，数据位全部反转了，而符号位保持不变，且移动到了最后一位。这一步真的写的很巧妙！

ZigZag还原代码如下：

functoInt32(zzint32)int32{

	returnint32(uint32(zz)>>1)^-(zz&1)

}

类似的，我们还原的代码就反过来写就可以了。不过这里要注意一点，就是右移的时候，需要用不带符号的移动，否则如果第一位是1的时，移动时会补1。所以，使用了无符号的移位操作uint32(zz)>>1。

好了，有了该算法，就可以得到一个有前导0的整数。只是，该数据依然使用4字节存储。下来我们要考虑如何尽可能的减少字节数，并且还能还原。

例如，我们将1按照如上算法转化得到：00000000000000000000000000000010。

下来我们最好只需要发送2bits（10），或者发送8bits（00000010），把前面的0全部省掉。因为数据传输是以字节为单位，所以，我们最好保持8bits这样的单位。所以我们有2种做法：

我们可以额外增加一个字节，用来表示接下来有效的字节长度，比如：0000000100000010，前8位表示接下来有1个字节需要传输，第二个8位表示真正的数据。这种方式虽然能达到我们想要的效果，但是莫名的增加一个字节的额外浪费。有没有不浪费的办法呢？
字节自表示方法。ZigZag引入了一个方法，就是用字节自己表示自己。具体怎么做呢？我们来看看代码。

funccompress(zzint32)[]byte{

	varres[]byte

	size:=binary.Size(zz)

	fori:=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

		}

	}

	returnres

}

大家先看看代码里那个^0x7F，他究竟是个什么数呢？

^0x7F：11111111111111111111111110000000

他就是从倒数第八位开始，高位全为1的数。他的作用就是去除最后七位后，判断还有没有信息。

我们把ZigZag值传递给这个函数，这个函数就将这个值从低位到高位切分成每7bits一组，如果高位还有有效信息，则给这7bits补上1个bit的1（0x80）。如此反复直到全是前导0，便结束算法。

举个例来讲：

十进制：-1000

→补：**1**1111111111111111111110000011000

→ZigZag：0000000000000000000001111100111**1**

我们先按照七位一组的方式将上面的数字划开，00000000000000000000011111001111。

详细步骤如下：

他跟^0x7F做与操作的结果，高位还有信息，所以，我们把低7位取出来，并在倒数第八位上补一个1（0x80）：11001111。
将这个数右移七位，00000000000000000000000000001111。
再取出最后的七位，跟^0x7F做与操作，发现高位已经没有信息了（全是0），那么我们就将最后8位完整的取出来：00001111，并且跳出循环，终止算法。
最终，我们就得到了两个字节的数据[11001111,00001111]。

通过上面几步，我们就将一个4字节的ZigZag变换后的数字变成了一个2字节的数据。如果我们是网络传输的话，就直接发送这2个字节给对方进程。对方进程收到数据后，就可以进行数据的组装还原了。具体的还原操作如下：

funcdecompress(zzByte[]byte)int32{

varresint32

fori,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

}

}

returnres

}

整个过程就和压缩的时候是逆向的，对于每一个字节，先看最高一位是否有1（0x80）。如果有，就说明不是最后一个数据字节包，那取这个字节的最后七位进行拼装。否则，说明就是已经到了最后一个字节了，那直接拼装后，跳出循环，算法结束。最终得到4字节的整数。

结语

算法不是很复杂，遇到哪块不懂了，就好好观察想想，这也是对Protobuf原理理解的重要部分。如果有不懂的，就在下方给我留言！

原文链接：

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

进制

三个东西

1.原码

2.反码

3.补码

ZigZag

结语

热门推荐

随机推荐