Go源碼和ProtoBuf中的Varint編碼和Zigzag編碼該如何理解

這篇文章主要為大家分析了Go源碼和ProtoBuf中的Varint編碼和Zigzag編碼該如何理解的相關(guān)知識(shí)點(diǎn)，內(nèi)容詳細(xì)易懂，操作細(xì)節(jié)合理，具有一定參考價(jià)值。如果感興趣的話，不妨跟著跟隨小編一起來(lái)看看，下面跟著小編一起深入學(xué)習(xí)“Go源碼和ProtoBuf中的Varint編碼和Zigzag編碼該如何理解”的知識(shí)吧。

成都創(chuàng)新互聯(lián)公司堅(jiān)持“要么做到，要么別承諾”的工作理念，服務(wù)領(lǐng)域包括：做網(wǎng)站、網(wǎng)站制作、企業(yè)官網(wǎng)、英文網(wǎng)站、手機(jī)端網(wǎng)站、網(wǎng)站推廣等服務(wù)，滿(mǎn)足客戶(hù)于互聯(lián)網(wǎng)時(shí)代的渾江網(wǎng)站設(shè)計(jì)、移動(dòng)媒體設(shè)計(jì)的需求，幫助企業(yè)找到有效的互聯(lián)網(wǎng)解決方案。努力成為您成熟可靠的網(wǎng)絡(luò)建設(shè)合作伙伴！

最近博主在看Go源碼，發(fā)現(xiàn)index/suffixarray下的后綴數(shù)組也有用到Varint編碼，又發(fā)現(xiàn)ProtoBuf也有類(lèi)似實(shí)現(xiàn)，原理都是一樣的，可能具體編碼方式有一點(diǎn)點(diǎn)不同。

為什么要用Varint編碼和Zigzag編碼，

1.我們先來(lái)看看各自的Varint編碼實(shí)現(xiàn)

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
}

兩者實(shí)現(xiàn)幾乎一樣，原理都是每7位作為有效位，最高位作為標(biāo)志位，表示數(shù)據(jù)后面還有還沒(méi)結(jié)束，需要循環(huán)讀取 注：16進(jìn)制0X80 == 10進(jìn)制128

2.最有趣的地方在ZigZag編碼實(shí)現(xiàn)

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的看著比較簡(jiǎn)單，直接把最高位的放到最后面，正數(shù)就會(huì)和負(fù)數(shù)交替出現(xiàn)，正數(shù)為偶數(shù)（原來(lái)的兩倍），負(fù)數(shù)為奇數(shù)（絕對(duì)值的兩倍-1） 例如：

• 0:0

• -1:1

• 1:2

• -2:3

• 2:4

我們來(lái)看Go源碼的實(shí)現(xiàn)，先將數(shù)字轉(zhuǎn)為uint64，負(fù)數(shù)在計(jì)算機(jī)會(huì)以補(bǔ)碼的形式存在， 例如-5的補(bǔ)碼為： 1111111111111111111111111111111111111111111111111111111111111011 然后左移一位得到ux的值： 1111111111111111111111111111111111111111111111111111111111110110 如果是正數(shù)是原來(lái)的兩倍，跟ZigZag是一樣的，因?yàn)檎龜?shù)的最高位是0 如果是負(fù)數(shù)還得ux取反，為9，負(fù)數(shù)為奇數(shù)（絕對(duì)值的兩倍-1），滿(mǎn)足ZigZag的原理： 0000000000000000000000000000000000000000000000000000000000001001

問(wèn)題就來(lái)了，為什么正數(shù)是對(duì)的，負(fù)數(shù)也是對(duì)的？

• 正數(shù)上面解釋過(guò)了，不管是將最高位移到最后一位還是左移一位都是擴(kuò)大兩倍，所以沒(méi)問(wèn)題

• 負(fù)數(shù)的話，要記住負(fù)數(shù)在計(jì)算機(jī)的編碼方式，使用補(bǔ)碼表示的，即補(bǔ)碼=反碼+1，理解這兩個(gè)為什么都可以就很容易了，其實(shí)不管是取反還是跟v>>31進(jìn)行異或，其實(shí)都是跟1111111111111111111111111111111111進(jìn)行異或，效果跟取反是相同的。

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

• i為正，右移高位補(bǔ)0，左移低位補(bǔ)0

• i為負(fù)，右移高位補(bǔ)1，左移低位補(bǔ)0

go是什么

golang是一種編譯語(yǔ)言，可以將代碼編譯為機(jī)器代碼，編譯后的二進(jìn)制文件可以直接部署到目標(biāo)機(jī)器而無(wú)需額外的依賴(lài)，所以golang的性能優(yōu)于其他的解釋性語(yǔ)言，且可以在golang中使用goroutine來(lái)實(shí)現(xiàn)并發(fā)性，它提供了一個(gè)非常優(yōu)雅的goroutine調(diào)度程序系統(tǒng)，可以很容易地生成數(shù)百萬(wàn)個(gè)goroutine。

關(guān)于“Go源碼和ProtoBuf中的Varint編碼和Zigzag編碼該如何理解”就介紹到這了,更多相關(guān)內(nèi)容可以搜索創(chuàng)新互聯(lián)以前的文章，希望能夠幫助大家答疑解惑，請(qǐng)多多支持創(chuàng)新互聯(lián)網(wǎng)站！

分享標(biāo)題：Go源碼和ProtoBuf中的Varint編碼和Zigzag編碼該如何理解
當(dāng)前鏈接：http://muchs.cn/article30/ipijpo.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供網(wǎng)站營(yíng)銷(xiāo)、網(wǎng)站內(nèi)鏈、網(wǎng)站設(shè)計(jì)、面包屑導(dǎo)航、關(guān)鍵詞優(yōu)化、網(wǎng)站建設(shè)

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶(hù)投稿、用戶(hù)轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請(qǐng)盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng)，如需處理請(qǐng)聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來(lái)源： 創(chuàng)新互聯(lián)