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編碼該如何理解”就介紹到這了,更多相關內容可以搜索億速云以前的文章，希望能夠幫助大家答疑解惑，請多多支持億速云網站！