Go源码和ProtoBuf中的Varint编码和Zigzag编码该如何理解

这篇文章主要为大家分析了Go源码和ProtoBuf中的Varint编码和Zigzag编码该如何理解的相关知识点，内容详细易懂，操作细节合理，具有一定参考价值。如果感兴趣的话，不妨跟着跟随小编一起来看看，下面跟着小编一起深入学习“Go源码和ProtoBuf中的Varint编码和Zigzag编码该如何理解”的知识吧。

最近博主在看Go源码，发现index/suffixarray下的后缀数组也有用到Varint编码，又发现ProtoBuf也有类似实现，原理都是一样的，可能具体编码方式有一点点不同。

为什么要用Varint编码和Zigzag编码，

1.我们先来看看各自的Varint编码实现

Go:

func EncodeVarInt64(v int) {
	var values []int
	for v >= 128 {
		values = append(values, (v&(128-1))|B)
		v >>= 7
	}
	values = append(values, v)
}

ProtoBuf:

func PutUvarint(buf []byte, x uint64) int {
	i := 0
	for x >= 0x80 {
		buf[i] = byte(x) | 0x80
		x >>= 7
		i++
	}
	buf[i] = byte(x)
	return i + 1
}

两者实现几乎一样，原理都是每7位作为有效位，最高位作为标志位，表示数据后面还有还没结束，需要循环读取 注：16进制0X80 == 10进制128

2.最有趣的地方在ZigZag编码实现

Go:

func PutVarint(buf []byte, x int64) int {
	ux := uint64(x) << 1
	if x < 0 {
		ux = ^ux
	}
	return PutUvarint(buf, ux)
}

ProtoBuf:

func Zigzag(v int32) int32 {
	return v<<1 ^ v>>31
}

ProtoBuf的看着比较简单，直接把最高位的放到最后面，正数就会和负数交替出现，正数为偶数（原来的两倍），负数为奇数（绝对值的两倍-1） 例如：

• 0:0

• -1:1

• 1:2

• -2:3

• 2:4

我们来看Go源码的实现，先将数字转为uint64，负数在计算机会以补码的形式存在， 例如-5的补码为： 1111111111111111111111111111111111111111111111111111111111111011 然后左移一位得到ux的值： 1111111111111111111111111111111111111111111111111111111111110110 如果是正数是原来的两倍，跟ZigZag是一样的，因为正数的最高位是0 如果是负数还得ux取反，为9，负数为奇数（绝对值的两倍-1），满足ZigZag的原理： 0000000000000000000000000000000000000000000000000000000000001001

问题就来了，为什么正数是对的，负数也是对的？

• 正数上面解释过了，不管是将最高位移到最后一位还是左移一位都是扩大两倍，所以没问题

• 负数的话，要记住负数在计算机的编码方式，使用补码表示的，即补码=反码+1，理解这两个为什么都可以就很容易了，其实不管是取反还是跟v>>31进行异或，其实都是跟1111111111111111111111111111111111进行异或，效果跟取反是相同的。

• i <<= 1 & i >>= 1

• i为正，右移高位补0，左移低位补0

• i为负，右移高位补1，左移低位补0

go是什么

golang是一种编译语言，可以将代码编译为机器代码，编译后的二进制文件可以直接部署到目标机器而无需额外的依赖，所以golang的性能优于其他的解释性语言，且可以在golang中使用goroutine来实现并发性，它提供了一个非常优雅的goroutine调度程序系统，可以很容易地生成数百万个goroutine。

关于“Go源码和ProtoBuf中的Varint编码和Zigzag编码该如何理解”就介绍到这了,更多相关内容可以搜索亿速云以前的文章，希望能够帮助大家答疑解惑，请多多支持亿速云网站！