中山市建设信息网站,快速建网站工具,个人网站设计与开发,学做网站要学什么语言文章目录 编码介绍无符号整数较小的值较大的值Go中的实现编码PutUvarint解码Uvarint 有符号整数较小的值(指绝对值)较大的负数(只绝对值)Go中的实现编码PutVarint解码Varint 总结 编码介绍
varint是一种将整数编码为变长字节的压缩编码算法#xff0c;本篇文章就是分析该编码… 文章目录 编码介绍无符号整数较小的值较大的值Go中的实现编码PutUvarint解码Uvarint 有符号整数较小的值(指绝对值)较大的负数(只绝对值)Go中的实现编码PutVarint解码Varint 总结 编码介绍
varint是一种将整数编码为变长字节的压缩编码算法本篇文章就是分析该编码算法的原理以及看一看go中的源码实现。
计算机中整型数据是按照补码进行存储的varint编码的原理就是将整数按照7bits划分在最高位设置一个有效位表示后面是否还有该整数的部分当最高位为1时表示后面还有该数据的字节为0表示该字节是最后一个字节。
无符号整数
较小的值
举个例子对于一个uint32来说无论数字多大都会占用4个字节的大小空间。对0000 0000 0000 0000 0000 0000 0000 0001 进行编码
首先将该数字按照7位进行分组
0000 0000000 0000000 0000000 0000001依次从低字节开始读发现只需要一个字节就能表示,后面没有可用的字节最高位置0
0000 0001所以最终对1的编码只占用一个字节
较大的值
对0000 1111 1111 0000 1111 0000 1111 1111 进行编码
首先按照7bit进行分组
0000 1111111 1000011 1100001 1111111依次读取低位字节进行编码
| 1111111 | 1100001 | 1000011 | 1111111 | 0000 || 11111111 | 11100001 | 11000011 | 01111111 | 所以最终该数字占用 4 个字节
Go中的实现
go中关于varint编码的实现在binary包下这里参考的是Go1.20
编码PutUvarint
func PutUvarint(buf []byte, x uint64) int {i : 0for x 0x80 {// 将该字节的最高位置 1 表示后面还有数据buf[i] byte(x) | 0x80// 将x向右移动7位(按照7bit进行分组的过程)x 7i}buf[i] byte(x)return i 1
}循环条件就是判断当前x的值是否能用一个字节表示大于0x80说明不能使用一个字节表示。
解码Uvarint
func Uvarint(buf []byte) (uint64, int) {var x uint64var s uint// 遍历buf中的每个字节低位字节表示原数据的高位for i, b : range buf {// 如果i达到了64位数据所能编码的最大字节数说明溢出if i MaxVarintLen64 {// Catch byte reads past MaxVarintLen64.// See issue https://golang.org/issues/41185return 0, -(i 1) // overflow}// 如果该字节小于0x80说明该字节是最后一个有效字节if b 0x80 {// 对于一个uint64的数据来说64 % 7 1所以最终只会多出1bit// 如果 b 1,说明原数据并不是64位的溢出if i MaxVarintLen64-1 b 1 {return 0, -(i 1) // overflow}return x | uint64(b)s, i 1}// 将b最高位置0加到x上x | uint64(b0x7f) ss 7}return 0, 0
}有符号整数
较小的值(指绝对值)
对原码为1000 0000 0000 0000 0000 0000 0000 0001 的负数进行编码
负数的补码 除符号位外的位取反 1
首先计算数字的补码负数的补码是除符号位外取反1
1111 1111 1111 1111 1111 1111 1111 1111按照7bit进行分组 | 1111 | 1111111 | 1111111| 1111111 | 1111111 |编码
| 1111111 | 1111111 | 1111111 | 1111111 | 1111 |
| 11111111 | 11111111 | 11111111 | 11111111 | 0000 1111 |所以最终-1占了5个字节
较大的负数(只绝对值)
对原码为1111 1111 1111 0000 0000 0000 0000 0001 的负数进行编码
首先计算数字的补码负数的补码是除符号位外取反1
1000 0000 0000 1111 1111 1111 1111 1111按照7bit进行分组
1000 0000000 0111111 1111111 1111111编码
| 1111111 | 1111111 | 0111111 | 0000000 | 1000 |
| 11111111 | 11111111 | 10111111 | 10000000 | 0000 1000 |由此可得最终占用5个字节
Go中的实现
编码PutVarint
妙
func PutVarint(buf []byte, x int64) int {// 去掉符号位忽略符号位的影响更方便处理ux : uint64(x) 1// 如果x为负数则对ux进行取反此时最低位一定是1// 而对于正数来说最低位始终为 0也为解码时判断正负做了铺垫if x 0 {ux ^ux}// 经过上面的处理ux 为 x 的绝对值return PutUvarint(buf, ux)
}解码Varint
func Varint(buf []byte) (int64, int) {ux, n : Uvarint(buf) // ok to continue in presence of error// 和上面的操作是相对的因为最低位原本不属于原数据x : int64(ux 1)// 如果 ux 最低位为 1说明原数据是负数取反if ux1 ! 0 {x ^x}return x, n
}总结
varint编码的思想是
对于小的数字使用更好的字节进行编码对于大的数字使用更多的字节进行编码
因为大多数时候我们的应用程序中会大量使用小的数字而只是少量使用大的数字所以使用varint压缩编码在一定程度上可以节省空间。
但是通过原始的算法思想对负数进行编码时由于负数在计算机中存储的特殊性所以不会起到很好的作用所以go在实对负数进行压缩编码时首先将负数转化为正数表示也就是取绝对值的操作并在解码时通过最后一位来判断原数据是正数还是负数这样varint对负数的压缩也同样效果很好。
