ZigZag编码
2024-10-20 16:16:47
ZigZag编码
在网络传输和数据存储场景中，需要对数据进行压缩。数据压缩的算法非常多，但大部分的数据压缩算法的原理是通过某种编码方式不存储数据中的0比特位，因此0比特位越多，数据压缩的效果越好。ZigZag编码就是一种增加0比例位的编码方式。下面使用Java语言来描述ZigZag编码。
一、编码
正数
假设数据类型为byte的正数11，其二进制表示为：00001011
- 数据左移一位:
00010110 - 符号位（正数的符号为0）放到最后一位：
00010110
负数
假设数据类型为byte的负数-11，其二进制在计算机中是用补码表示的，计算过程如下。
正数原码：00001011。
反码：11110100
补码（反码加1）：11110101
处理过程：
- 左移一位：
11101010 - 符号位放到最后一位:
11101011 - 除最后一位外全部取反:
00010101
结论
正数经过处理后，前导0和后置0的个数不变。但是负数经过处理后，增加了三个前导0，可以用于压缩。
结合两种情况得出byte类型数据的编码公式：
ZigZag(n) = n>>7 ^ n<<1
-11的处理过程如下：
11110101 >> 7 = 1111111111110101 << 1 = 1110101011111111^11101010 = 00010101
二、解码
ZigZag的逆函数：
\(ZigZag^{-1}(n)\)=(n>>>1)^ -(n&1)
负数00010101的解码过程：
n>>>1：
00001010n&1：
00000001-(n&1):
111111111111111^0000101=11110101
最新文章
- Vertica参数的设置
- 「2014-3-13」Javascript Engine, Java VM, Python interpreter, PyPy – a glance
- 【USACO 1.2】Palindromic Squares
- s3c2440 移值u-boot-2016.03 第1篇 新建单板
- Mac上常用的一些命令
- HW4.20
- Android-版本与api对应关系图
- 【Java 之 JVM】Java内存结构概述
- JSP page指令
- Python注释用法
- puppeteer，新款headless chrome！
- 表单数据验证方法（二）——ASP.NET后台验证
- c/c++ llinux epoll系列5 解除epoll_wait状态
- selenium的基本用法
- bae64编码
- 卷积的三种模式:full, same, valid
- jquery 数组的操作
- System.getSecurityManager()
- 使用Samba实现文件共享
- Daily Scrum - 12/02