zigzag算法详解 | Zig Zag 算法
zigzag算法详解sif_6662020-12-1822:13:401749收藏3分类专栏：c文章标签：算法c版权声明：本文为博主原创文章，遵循CC4.0BY版权协议，转载请附上原文出处链接和本声明。
本文链接：https://blog.csdn.net/weixin_43708622/article/details/111397290版权c专栏收录该内容20篇文章1订阅订阅专栏zigzag编码的出现是为了解决varint对负数编码效率低的问题。
zigzag编码的原理非常简单，就是将有符号整数映射为无符号整数。
在实现上，映射通过移位即可实现，而不需要使用映射表来存储。
zigzag编码原理解析对于正整数，可以把无意义的0去掉，只存储从1开始的"有效"数据，这样就可以压缩数据了。
例如，对于正整数1，其补码(当代计算机中实际按补码表示整数)按位展开，即为(00000000000000000000000000000001)补，显然，我们可以只用一个字节甚至1bit来存储有效数据。
负数的补码可没有这么容易压缩。
例如，对于负数-1，(11111111111111111111111111111111)补，全为1，并没有压缩的空间了啊！怎么办？我们知道补码的最高位是符号位，对于负数，符号位为1，它阻碍了对于无意义0的压缩；既然有阻碍，那就得想办法解决这个阻碍；是否可以将符号位移动到补码的最后，然后数据位整体左移1位，这样就能把这个“阻碍”解决呢？(-1)10(11111111111111111111111111111111)补符号位移动到最低位，数据位整体相对左移1位(11111111111111111111111111111111)移位对于绝对值小的负数，冗余的前导1还是很多；似乎解决的并不彻底把数据位按位取反，符号位保持不变(00000000_00000000_00000000_00000001)取反经过移位和取反操作后，-1被“编码”成了1。
如此，便能很好的压缩数据，彩！对于非负整数，只需完成符号位移到最低位，数据位整体左移1位我们再来看看整数1通过同样的处理后被“编码”成什么值。
(1)10(00000000000000000000000000000001)补(00000000000000000000000000000010)移位经过移位操作后，1被“编码”成了2。
似乎能得到这样的结论：对于负数，经过移位和数据位取反，也能将绝对值小的负数进行压缩；对于非负数，经过移位，也可以压缩；那么又有一个问题来了，这两种结论怎样在代码实现层面合二为一呢？知识点：算术左移低位补0；算术右移，若符号位为0，高位补0；若符号位为1，高位补1；对于n=-1(32位)，(11111111111111111111111111111111)补n<<1，a=(11111111111111111111111111111110)补，数据位整体左移1位n>>31，b=(11111111111111111111111111111111)补，符号位移到最低位负数的算数右移高位补1，所以右移31位后，b为全1，这点非常重要c=a^b，c=(0000000000000000000000000000001)补，将-1“编码”成了1，与前面的分析一致因为a中数据位冗余的前导1刚好与b中数据位冗余的前导1相对应，那么进行异或操作时，就能将这些冗余的前导1消除掉，数据位完成了取反动作，这样便能压缩数据了对于n=1(32位)，(00000000000000000000000000000001)补n<<1，a=(00000000000000000000000000000010)补，数据位整体左移1位n>>31，b=(00000000000000000000000000000000)补，符号位移到最低位非负数的算数右移高位补0，所以右移31位后，b全为0，这点非常重要c=a^b，c=(00000000000000000000000000000010)补，将1“编码”成了2，与前面的分析一致因为0^0还是0，所以对于正整数，异或操作没有影响。
综上所述，对于32位整数，(n<<1)^(n>>31)，即能实现zigzag编码。
如此精妙，彩！搞懂了zigzag的编码原理，当然得知道怎样解码，否则就不能还原真实数值了。
zigzag解码原理解析对于zigzag编码的值2，(00000000000000000000000000000010)补n>>1，a=(0000000000000000000000
本文链接：https://blog.csdn.net/weixin_43708622/article/details/111397290版权c专栏收录该内容20篇文章1订阅订阅专栏zigzag编码的出现是为了解决varint对负数编码效率低的问题。
zigzag编码的原理非常简单，就是将有符号整数映射为无符号整数。
在实现上，映射通过移位即可实现，而不需要使用映射表来存储。
zigzag编码原理解析对于正整数，可以把无意义的0去掉，只存储从1开始的"有效"数据，这样就可以压缩数据了。
例如，对于正整数1，其补码(当代计算机中实际按补码表示整数)按位展开，即为(00000000000000000000000000000001)补，显然，我们可以只用一个字节甚至1bit来存储有效数据。
负数的补码可没有这么容易压缩。
例如，对于负数-1，(11111111111111111111111111111111)补，全为1，并没有压缩的空间了啊！怎么办？我们知道补码的最高位是符号位，对于负数，符号位为1，它阻碍了对于无意义0的压缩；既然有阻碍，那就得想办法解决这个阻碍；是否可以将符号位移动到补码的最后，然后数据位整体左移1位，这样就能把这个“阻碍”解决呢？(-1)10(11111111111111111111111111111111)补符号位移动到最低位，数据位整体相对左移1位(11111111111111111111111111111111)移位对于绝对值小的负数，冗余的前导1还是很多；似乎解决的并不彻底把数据位按位取反，符号位保持不变(00000000_00000000_00000000_00000001)取反经过移位和取反操作后，-1被“编码”成了1。
如此，便能很好的压缩数据，彩！对于非负整数，只需完成符号位移到最低位，数据位整体左移1位我们再来看看整数1通过同样的处理后被“编码”成什么值。
(1)10(00000000000000000000000000000001)补(00000000000000000000000000000010)移位经过移位操作后，1被“编码”成了2。
似乎能得到这样的结论：对于负数，经过移位和数据位取反，也能将绝对值小的负数进行压缩；对于非负数，经过移位，也可以压缩；那么又有一个问题来了，这两种结论怎样在代码实现层面合二为一呢？知识点：算术左移低位补0；算术右移，若符号位为0，高位补0；若符号位为1，高位补1；对于n=-1(32位)，(11111111111111111111111111111111)补n<<1，a=(11111111111111111111111111111110)补，数据位整体左移1位n>>31，b=(11111111111111111111111111111111)补，符号位移到最低位负数的算数右移高位补1，所以右移31位后，b为全1，这点非常重要c=a^b，c=(0000000000000000000000000000001)补，将-1“编码”成了1，与前面的分析一致因为a中数据位冗余的前导1刚好与b中数据位冗余的前导1相对应，那么进行异或操作时，就能将这些冗余的前导1消除掉，数据位完成了取反动作，这样便能压缩数据了对于n=1(32位)，(00000000000000000000000000000001)补n<<1，a=(00000000000000000000000000000010)补，数据位整体左移1位n>>31，b=(00000000000000000000000000000000)补，符号位移到最低位非负数的算数右移高位补0，所以右移31位后，b全为0，这点非常重要c=a^b，c=(00000000000000000000000000000010)补，将1“编码”成了2，与前面的分析一致因为0^0还是0，所以对于正整数，异或操作没有影响。
综上所述，对于32位整数，(n<<1)^(n>>31)，即能实现zigzag编码。
如此精妙，彩！搞懂了zigzag的编码原理，当然得知道怎样解码，否则就不能还原真实数值了。
zigzag解码原理解析对于zigzag编码的值2，(00000000000000000000000000000010)补n>>1，a=(0000000000000000000000