ProtoBuf中的varint zigzag编码原理学习

varint 用可变的字节数来存储数字，达到压缩目的，基于的思想是，小的数字出现的频率比大的数字出现频率大很多
zigzag 主要解决varint对负数无法压缩的问题，将负数映射为正数，再用varint压缩

参考资料：

• 简洁的说明
  木犀互联网技术周刊（第四十期）: 面对小数值的高效率序列化方案:varints和zigzag编码
  深入 ProtoBuf - 编码
• zigzag去负数原理
  为什么-128的补码是1000 0000？
  原码、反码、补码 详解！不懂的请看过来！
• 算法，可以自己去推导
  ZigZag编码
• 参考代码
  C# -- varint编码实现（编码、解码）

源码

namespace VarintZigzigDemo
{
    /// <summary>
    /// https://blog.csdn.net/honey199396/article/details/106909428
    /// </summary>
    public class VarintUtils
    {

        public static byte[] VarintEncode(uint value, int length)
        {
            var buffer = new byte[length];
            int index = 0;
            while (true)
            {
                //0x7F 即　0111 1111
                //~ 表示取反  
                if ((value & ~0x7F) == 0)
                {
                    buffer[index] = (byte) (value & 0x7F);
                    break;
                }
                else
                {
                    //取出7位并在第8位加上标记1
                    buffer[index] = (byte)((value & 0x7F) | 0x80);
                    index++;
                    //已经处理的舍去
                    value = value >> 7;
                }
            }

            return buffer;
        }

        public static uint VarintDecode(byte[] buffer)
        {
            int value = 0;

            var len = buffer.Length;
            for (int i = 0; i < len; i++)
            {
                byte b = buffer[i];
                //0x7F 即　0111 1111
                //取出7位然后右移，因为是小端存储
                value |= (b & 0x7F) << (i * 7);
                // 0x80 即 1000 0000
                //第8位是0 说明后面没有字节了
                if ((byte) (b & 0x80) == 0)
                {
                    break;
                }
            }
            return (uint)value;
        }

        public static int VarintSize(uint value)
        {
            //位置7位，如果前面都为0，说明只有一个有效字节
            if ((value & (0xFFFFFFFF << 7)) == 0)
            {
                return 1;
            }

            if ((value & (0xFFFFFFFF << 14)) == 0)
            {
                return 2;
            }

            if ((value & (0xFFFFFFFF << 21)) == 0)
            {
                return 3;
            }

            if ((value & (0xFFFFFFFF << 28)) == 0)
            {
                return 4;
            }
            return 5;
        }


        public static uint ZigZagEncode(int n)
        {
            return (uint)((n >> 31) ^ (n << 1));
        }

        public static int ZigZagDecode(uint n)
        {
            return (int)((n >> 1) ^ -(n & 1));
        }
    }
}

using System;

namespace VarintZigzigDemo
{
    class Program
    {
        static void Main(string[] args)
        {
            Test(0);
            Test(127);
            Test(-127);
            Test(sbyte.MaxValue);
            Test(sbyte.MinValue);
            Test(short.MaxValue);
            Test(short.MinValue);
            Test(int.MaxValue);
            Test(int.MinValue);

            Console.ReadKey();
        }

        private static void Test(int value)
        {
            //负数转正数
            var n = VarintUtils.ZigZagEncode(value);
            //要占用的字节长度
            var len = VarintUtils.VarintSize(n);
            //字节流
            var buffer = VarintUtils.VarintEncode(n, len);
            //varint 解析
            var nn = VarintUtils.VarintDecode(buffer);
            //还原
            var nn2 = VarintUtils.ZigZagDecode(nn);
            Console.WriteLine($" raw:{value}  zzen:{n}  varde:{nn} zzde:{nn2} len:{len}");
        }
    }
}

gitee源码