ZigZag 编码

在计算机 32 位系统中，2 和 -2 的二进制表示如下：

• 2的二进制表示：00000000 00000000 00000000 00000010

• -2的二进制表示：11111111 11111111 11111111 11111110

其中，最高位为符号位，0 表示正数，1 表示负数，其余位为数值位。因此，2 的符号位为 0，其余位为 2 的二进制表示；-2 的符号位为 1，其余位为 2 的补码表示。

如果 64 位系统就需要 64 byte，如果在网络中传输一个 64 位整数就需要传输 64 个 byte。那有没有办法压缩呢？

ZigZag 编码是一种在 Protocol Buffers 中使用的整数压缩算法，它可以将有符号整数压缩为无符号整数，以减少存储空间的使用。

对于一个有符号整数 $n$，将其编码为一个无符号整数 $m$：

• 如果 $n$ 是正整数，则将 $n$ 左移一位。
• 如果 $n$ 是负整数，则将 $n$ 左移一位，数据位求反。

十进制 1：

• 二进制：00000000 00000000 00000000 00000001
• ZigZag：00000000 00000000 00000000 00000010

十进制 -2：

• 二进制：11111111 11111111 11111111 11111110
• ZigZag
  • 左移一位：11111111 11111111 11111111 11111101
  • 数据位求反：00000000 00000000 00000000 00000011

实现方式

1
2

def zigzag_encode (x):
   return (x << 1) ^ (x >> 31)

上式中 x >> 31 表示将 x 的符号位（即最高位）扩展到其他位，得到一个全 1 或全 0 的二进制数，例如 x 为正数时为 0，为负数时为 -1。

• 当 x 为负数时，右移操作会将符号位扩展到其他位，得到一个正整数，左移操作将其乘以 2，最后进行异或操作，得到 ZigZag 编码；
• 当 x 为非负数时，左移操作将其乘以 2，得到的结果就是 ZigZag 编码。

1
2

def zigzag_decode (z):
    return (z >> 1) ^ -(z & 1)

上式中 z >> 1 表示将 z 右移一位，得到原来的无符号整数，(z & 1) 表示取 z 的最低位，当其为 0 时表示原数为非负数，为 1 时表示原数为负数，最后根据该值取反并异或右移后的无符号整数，得到原来的有符号整数。

zigzag-encoding