ZigZag是一种针对整数的编码算法。

1.ZigZag编码

编码就是将整数进行转换的过程。

1.1.编码规则

满足两个规则

（1）将整数的补码的最高位移动到最低位。

（2）如果是负数，则除符号位外，其他位取反；正数无须操作。

1.2.编码公式

可通过以下公式实现zigzag编码。

# 针对8位整数的编码
zigzag(n) = n>>7 ^ n<<1

# 针对32位整数的编码
zigzag(n) = n>>31 ^ n<<1

编码与整数的bit位数有关。

1.3.编码案例

32位整数11的编码过程

# 原码十进制
11

# 原码二进制
00000000,00000000,00000000,00001011

# 补码二进制
00000000,00000000,00000000,00001011

# 最高位移到最低位
00000000,00000000,00000000,00010110

# ZigZag编码
00000000,00000000,00000000,00010110

32位整数-11的编码过程

# 原码十进制
-11

# 原码二进制（负数用补码表示）
11111111,11111111,11111111,11110101

# 补码二进制
11111111,11111111,11111111,11110101

# 最高位移到最低位
11111111,11111111,11111111,11101011

# 除最后一位外（符号位），其他位取反
00000000,00000000,00000000,00010101

# ZigZag编码
00000000,00000000,00000000,00010101

正数的补码为原码本身，负数的补码为反码加1

可以看到，无论是正数还是负数，经过ZigZag编码后，高位大概率是0，可用于压缩。

2.ZigZag解码

解码就是将编码后的整数转换为原文本的过程。

2.1.解码规则

满足以下两个规则

（1）如果最低位是1，表示负数，除符号位外，其他位取反；如果最低位是0，则表示正数，无须操作

（2）将整数补码最低位移动到最高位

2.2.解码公式

可通过以下公式实现zigzag解码。

zigzag'(n) = (n>>>1) ^ -(n&1)

这里不需要考虑位数

2.3.解码案例

以下是一个正数的解码过程

# 二进制zigzag编码
00000000,00000000,00000000,00010110

# 最低位是1，表示正数，无须操作
00000000,00000000,00000000,00010110

# 最低位移到最高位
00000000,00000000,00000000,00001011

# 得到整数
11

以下是一个负数的解码过程

# 二进制zigzag编码
00000000,00000000,00000000,00010101

# 最低位是1，表示负数，其他位取反
11111111,11111111,11111111,11101011

# 最低位移到最高位
11111111,11111111,11111111,11110101

# 取补码（反码加1）
00000000,00000000,00000000,00001011

# 得到整数
-11

3.ZigZag适用场景

ZigZag仅从经验出发，认为较小的整数会有较大的概率出现，故设计编码策略：小整数对应的ZigZag码字短，大整数对应的ZigZag码字长。

但是，在特定的场景下，比如，要传输的整数为大整数居多，ZigZag编码的压缩效率就不理想了。