Protocol Buffers的Varint编码与ZigZag原理
解释Protobuf中Varint编码的压缩原理，包括Base 128 Varint的编码方式、负数的处理（ZigZag）、以及Field Key的计算规则（wire type + field number）。
回答
Yahuda
1. Varint编码原理
- 每个字节使用7位存储数据，最高位（MSB）作为延续标志位
- MSB=1：后续还有字节
- MSB=0：此为最后一个字节
- 小整数占用很少字节（如127仅1字节，但16384需要3字节）
- 示例：300的Varint编码
- 300 = 256 + 44 = 0000_0001_0010_1100
- 逆序分7位：010_1100 000_0010
- 加MSB：1010_1100 0000_0010 → [0xAC, 0x02]
2. ZigZag编码（处理负数）
- 负数在Varint中会占10字节（因为符号位），效率极低
- ZigZag将负数映射为正数：
n → (n << 1) ^ (n >> 31) // sint32 n → (n << 1) ^ (n >> 63) // sint64 - 效果：-1 → 1, 1 → 2, -2 → 3, 2 → 4...
- 适用于有符号整数场景
3. Wire Type与Field Key
- Key = (field_number << 3) | wire_type
- Wire Type 0：Varint（int32/uint64/bool/enum）
- Wire Type 1：64-bit（fixed64/sfixed64/double）
- Wire Type 2：Length-delimited（string/bytes/embedded message/repeated）
- Wire Type 5：32-bit（fixed32/sfixed32/float）
- 解码时通过Key知道字段编号和数据类型
4. 编码优势
- 消息体紧凑，无冗余字段名
- 兼容性：新字段用新编号，旧客户端可忽略