网站建设课程毕设,网站备案信息被工信部删除,推广普通话喜迎二十手抄报,网站群建设标准zigzag编码的出现是为了解决varint对负数编码效率低的问题。zigzag编码的原理非常简单#xff0c;就是将有符号整数映射为无符号整数。在实现上#xff0c;映射通过移位即可实现#xff0c;而不需要使用映射表来存储。 zigzag编码原理解析
对于正整数#xff0c;可以把无意…zigzag编码的出现是为了解决varint对负数编码效率低的问题。zigzag编码的原理非常简单就是将有符号整数映射为无符号整数。在实现上映射通过移位即可实现而不需要使用映射表来存储。 zigzag编码原理解析
对于正整数可以把无意义的0去掉只存储从1开始的有效数据这样就可以压缩数据了。
例如对于正整数1其补码(当代计算机中实际按补码表示整数)按位展开即为(00000000 00000000 00000000 00000001)补显然我们可以只用一个字节甚至1bit来存储有效数据。
负数的补码可没有这么容易压缩。
例如对于负数-1(11111111 11111111 11111111 11111111)补全为1并没有压缩的空间了啊怎么办
我们知道补码的最高位是符号位对于负数符号位为1它阻碍了对于无意义0的压缩既然有阻碍那就得想办法解决这个阻碍是否可以将符号位移动到补码的最后然后数据位整体左移1位这样就能把这个“阻碍”解决呢
(-1)10
(11111111 11111111 11111111 11111111)补
符号位移动到最低位数据位整体相对左移1位
(11111111 11111111 11111111 11111111)移位
对于绝对值小的负数冗余的前导1还是很多似乎解决的并不彻底
把数据位按位取反符号位保持不变
(00000000_00000000_00000000_00000001)取反
经过移位和取反操作后-1被“编码”成了1。如此便能很好的压缩数据彩
对于非负整数只需完成 符号位移到最低位数据位整体左移1位
我们再来看看整数1通过同样的处理后被“编码”成什么值。
(1)10
(00000000 00000000 00000000 00000001)补
(00000000 00000000 00000000 00000010)移位
经过移位操作后1被“编码”成了2。
似乎能得到这样的结论 对于负数经过移位和数据位取反也能将绝对值小的负数进行压缩 对于非负数经过移位也可以压缩
那么又有一个问题来了这两种结论怎样在代码实现层面合二为一呢 知识点 算术左移低位补0算术右移若符号位为0高位补0若符号位为1高位补1 对于n-1(32位)(11111111 11111111 11111111 11111111)补
n 1 a (11111111 11111111 11111111 11111110)补数据位整体左移1位
n 31b (11111111 11111111 11111111 11111111)补符号位移到最低位
负数的算数右移高位补1所以右移31位后b为全1这点非常重要
ca^b c (00000000 00000000 0000000 00000001)补将-1“编码”成了1与前面的分析一致
因为a中数据位冗余的前导1刚好与b中数据位冗余的前导1相对应那么进行异或操作时就能将这些冗余的前导1消除掉数据位完成了取反动作这样便能压缩数据了
对于n1(32位)(00000000 00000000 00000000 00000001)补
n 1 a (00000000 00000000 00000000 00000010)补数据位整体左移1位
n 31b (00000000 00000000 00000000 00000000)补符号位移到最低位
非负数的算数右移高位补0所以右移31位后b全为0这点非常重要
ca^bc (00000000 00000000 00000000 00000010)补将1“编码”成了2与前面的分析一致
因为0^0还是0所以对于正整数异或操作没有影响。
综上所述对于32位整数(n1)^(n31)即能实现zigzag编码。如此精妙彩
搞懂了zigzag的编码原理当然得知道怎样解码否则就不能还原真实数值了。
zigzag解码原理解析
对于zigzag编码的值2(00000000 00000000 00000000 00000010)补
n 1 a (00000000 00000000 00000000 00000001)补整体右移还原数据位
-(n1)b -(21)10 -(0)10 (00000000 00000000 00000000 00000000)补最低位按位与取负号还原符号位
ca^bc (00000000 00000000 00000000 00000001)补将zigzag编码值2 解码还原成了1
对于zigzag编码的值3(00000000 00000000 00000000 00000011)补
n 1 a (00000000 00000000 00000000 00000001)补整体右移还原数据位
-(n1)b -(31)10 -(1)10 (11111111 11111111 11111111 11111111)补最低位按位与取负号还原符号位
ca^bc (11111111 11111111 11111111 11111110)补将zigzag编码值3 解码还原成了-2
综上所述对于32位整数(n1)^-(n1)即能实现zigzag解码。
c实现
// zigzag 编码
uint32_t zigzag_encode_32(int32_t val)
{return (uint32_t)((val1)^(val31));
}// zigzag解码
int32_t zigzag_decode_32(uint32_t val)
{return (int32_t)((val1) ^ -(val1));
}运行结果
$ ./a.out -1
input num:-1
zigzag code:1,0x1
zigzag decode:-1,0xffffffffffffffff
$ ./a.out -2147483648
input num:-2147483648
zigzag code:4294967295,0xffffffff
zigzag decode:-2147483648,0xffffffff80000000$ ./a.out 2147483647
input num:2147483647
zigzag code:4294967294,0xfffffffe
zigzag decode:2147483647,0x7fffffff所谓数据压缩说白了就是将不重要的数据忽略或舍弃由于计算机中只有0和1本质上就是将无意义的0丢弃而起到数据压缩的目的。
