ZigZag

ZigZag是一种压缩算法, 可以对小负数进行有效的压缩

在了解算法前, 首先需要知道计算机使用补码存储数据

• 原码: 最高位位符号位, 剩下的表示绝对值
• 反码: 除了符号位外, 对原码剩下的位取反
• 补码: 对于正数和零补码就是其原码, 对于负数的补码则是其反码+1

由于计算机使用补码存储数据, 二进制数据非常大, 在普通的去零压缩中没有优势
ZigZag是将符号位移动到最低位, 若是负数则再对除符号位之外数据位取反
相当于原码, 只是符号位在最低位

// 编码过程
-2                                  // 十进制
10000000 00000000 00000000 00000010 // 原码
11111111 11111111 11111111 11111110 // 补码
// ZigZag
-2 << 1 // 数据整体往左移动一位, 低位补0
11111111 11111111 11111111 11111100
-2 >> 31 // 将符号位移动到最低位, 由于是负数所以高位补1
11111111 11111111 11111111 11111111
(-2 << 1) ^ (-2 >> 31)  // 相当于返回了原码，只是将符号位放置在了最低位
n = 00000000 00000000 00000000 00000011

// 解码过程
n >> 1 // 右移，还原数据位
00000000 00000000 00000000 00000001
-(n & 1) // 还原符号位
00000000 00000000 00000000 00000001
(n >> 1) ^ (-(n & 1))
11111111 11111111 11111111 11111110

数据与编码对对应关系, 也是名称的由来