Zigzag 压缩小整数

zigzag 是一个简单好用的小整数压缩算法。

原理

现在一般的计算机都是 32 位或者 64 位机了，每个数据的表示长度和范围都比较多。一个常见的数据类型 int 一般占 4 个字节，但是在实际使用时，数字并不会很大，经常不会超过几万（当然要看实际情况），比如下面几个例子

number: 23
bit:    0000 0000 0000 0000 0000 0000 0001 0111
number: -33
bit:    1111 1111 1111 1111 1111 1111 1101 1111

通过观察可以发现，小正数的左侧有大量的 0，小负数的左侧有大量的 1。zigzag 做的就是将左边的冗余数据全部换为 0，便于后续压缩。

正数

拿 23 举例

1. 将数字左移一位：0000 0000 0000 0000 0000 0000 0010 1110
2. 符号位加到最后一位（正数符号位为 0 不用操作）

得到了最后的压缩结果：0000 0000 0000 0000 0000 0000 0010 1110

负数

拿 -33 举例

1. 左移一位：1111 1111 1111 1111 1111 1111 1011 1110
2. 符号位加到最后一位：1111 1111 1111 1111 1111 1111 1011 1111
3. 除最后一位全部取反：0000 0000 0000 0000 0000 0000 0100 0001

得到了最后的压缩结果：0000 0000 0000 0000 0000 0000 0100 0001

解码

$Zigzag^{-1}(n)$ = (n << 1) ^ -(n & 1)

实现

uint32_t EncodeInt(int32_t number) {
  return number < 0 ? (((uint32_t)(-number)) * 2 - 1) : number * 2;
}

int32_t DecodeInt(uint32_t number) {
  return (number >> 1) ^ -(number & 1);
}

下图是测试数字 -23 的结果：