LawrencePeng's Blog

专注收集代码小精灵

Zigzag编码

  • 目的
    • 基于经验，我们需要序列化的数据，通常小数（绝对值）多，大数少，所以出现了ZigZag编码，来减少编码数据的大小。

  • 过程

    • 双射

      • 构建一个F(int) -> int，让绝对值小的数尽量小，绝对值大的数尽量大。

      • 1
        n = (n << 1) ^ (n >> 31);

      • example

        • 0 -> 0
        • -1 -> 1
        • 1 -> 2
        • -2 -> 3
        • 2 -> 4

    • 变长编码

      • 代码

      • 1
        2
        3
        4
        5
        6
        7
        8
        9
        10
        11
        12
        13
        14
        15
        16
        17
        18
        19
        20
        21
        22
        23
        public static int encodeInt(int n, byte[] buf, int pos) {
        // move sign to low-order bit, and flip others if negative
          n = (n << 1) ^ (n >> 31);
          int start = pos;
          if ((n & ~0x7F) != 0) {
            buf[pos++] = (byte)((n | 0x80) & 0xFF);
            n >>>= 7;
            if (n > 0x7F) {
              buf[pos++] = (byte)((n | 0x80) & 0xFF);
              n >>>= 7;
              if (n > 0x7F) {
                buf[pos++] = (byte)((n | 0x80) & 0xFF);
                n >>>= 7;
                if (n > 0x7F) {
                  buf[pos++] = (byte)((n | 0x80) & 0xFF);
                  n >>>= 7;
                }
              }
            }
          } 
          buf[pos++] = (byte) n;
          return pos - start;
        }
      • 1
        2
        3
        4
        5
        6
        7
        8
        9
        等价于：
        while
            if 第七位满1或有进位:
                n |= 0x80;
                取低位的8位作为一个byte写入buf;
                n >>>=7（无符号右移7位，在高位插0）;
            else:
                取低位的8位作为一个byte写入buf
        end
CodeZigzag