做序列化优化做久了，你会对“负数”这两个字特别敏感。像 Protocol Buffers 这类依赖 Varint 编码的框架，处理正数时非常漂亮：小数字压得又细又薄，几字节就搞定。可一旦字段值变成负数，编码流水就一下子膨胀，肉眼可见的浪费。后来我翻源码时注意到一种叫 zigzag 的编码方案，专门为解决这问题而生。它做了一件很“拧巴”的事：把最高位的符号信息，直接挪到最低位，把负数重新整理成一串小无符号整数，再交给 Varint 去压缩。就是这样一步看似不起眼的变换，让我手里的日志协议包“瘦”了一大圈。
这篇内容既适合刚接触编码原理、想搞懂 ZigZag 到底是什么的初学者，也适合在调参序列化协议、反复纠结 int32 和 sint32 选型的后端开发。我会把原理、公式、手写实现和真实压测数据都串起来，最后再告诉你哪些地方容易踩坑。
1. 一个反直觉的起点：负数为什么难压缩
1.1 先认识 Varint，它其实是给“小整数”开的专用通道
Varint 本质上是一种可变长编码，也叫 LEB128 或 LEB128 的一种变体。它固定把每个字节的低 7 位当作数据位，最高位当作“续位”。如果最高位为 1，说明后面还有字节；如果最高位为 0，说明这是最后一个字节。读者一看就明白，这设计天然偏向小整数：数字越小，用到的字节越少，1 个字节就能装下 0 到 127。
举个例子：300 这个数，二进制是 100101100，超过 7 位，所以要分成两段来存。Varint 编码结果是0xAC 0x02，两个字节。如果是 1，那直接就是0x01，一个字节。说白了，Varint 就像自助餐厅里的迷你份餐盒：胃口小的人吃小份，你的钱包按份数付钱，自然越少越好。
1.2 补码的高位连续 1：负数的“膨胀陷阱”
问题来了，负数的二进制表示用的是补码。补码有一个“反直觉”的特征：一个数值上很小的负数，比如 -1，在 32 位整数里是11111111 11111111 11111111 11111111，看起来是 32 个 1。而 -63、-64 这类数字，高位也都是连续一堆 1。
Varint 按每 7 位切一段，并且只有当“这一段的值全为 0”时才可能结束。但对负数来说，高位连续是 1，几乎每一个 7 位分组的二进制都不是 0，编码器根本没有机会提前收工，只能一路把续位置 1，直到把所有位都搬完。于是 -1 这样一个很“小”的负数，跑进 Varint 里反而要吃满 5 个字节（32 位视角下）：
0xFF 0xFF 0xFF 0xFF 0x0F而 1 只需要0x01。同样是 1 的绝对值，符号一翻转，体积差了整整 4 倍。如果按照 Protocol Buffers 里 int32 的实现细节，负数还会先被符号扩展成 64 位，再走 Varint，-1 会直接吃掉 10 个字节。这是很多做协议优化的人第一次抓狂的地方：明明业务数据全是温度、偏移量、增量差值这类“绝对值不大”的负数，日志一条却胖得离谱。
1.3 负数为什么不能直接位移、取绝对值
有人可能会想：把负数的符号去掉，取个绝对值，再存一个“符号位”不就行了吗？思路是对的，但直接实现有几个麻烦。首先，绝对值方案面临INT_MIN这个边界，-2147483648 的绝对值在 32 位整数里根本表示不下，直接溢出。更关键的是：如果你用一个额外的位来存符号，仍然要回答“符号位放哪个位置”的问题。如果放在最高位，小负数依然会被顶到高位区间，Varint 依然没法提前结束，等于白干。如果放在最低位，又会破坏正数原本干净的位模式，让正数编码也跟着变长。
zigzag 其实就是做到了“符号放到最低位”这件事，但用一种极其精巧的位运算方式，把整数映射成连续的小无符号数，而且完全不依赖取绝对值。它不是在压缩数据，而是在给数据“排队”，让负数也站到 Varint 的舒适区里去。
2. ZigZag 的映射思想：一张折线图解决符号问题
2.1 一张表看懂映射关系
ZigZag 这个名字起得很形象。从 0 出发，它把整数按“之”字形排列：0、-1、1、-2、2、-3、3……对应到非负整数就是 0、1、2、3、4、5、6……就像折线一样来回穿梭。列成表格是这样：
| 原始整数 n | ZigZag 映射值 z |
|---|---|
| 0 | 0 |
| -1 | 1 |
| 1 | 2 |
| -2 | 3 |
| 2 | 4 |
| -3 | 5 |
| 3 | 6 |
| ... | ... |
| 2147483647 | 4294967294 |
| -2147483648 | 4294967295 |
看这张表能发现两个关键信息：一是负数和正数交替出现，绝对值越小的数字，对应的 ZigZag 值也越小；二是在 32 位范围内，映射后的值是“无符号视角”下的连续整数，换成 Varint 编码时，原本需要 5 字节甚至 10 字节的负数，现在可能只要 1 个字节。
2.2 公式推导：左移一位，再和符号位异或
32 位 ZigZag 编码公式很简洁：
z = (n << 1) ^ (n >> 31)这里n >> 31是算术右移，行为很关键：
- n 是正数或 0 时，算术右移 31 位得到 0；
- n 是负数时，算术右移 31 位得到 -1，也就是 32 位全 1。
所以公式可以拆成两种情况看。正数时，n >> 31为 0，异或等于没做，结果是n << 1，相当于把 n 映射到偶数位上：0 → 0，1 → 2，2 → 4。负数时，(n << 1)再去异或全 1，相当于按位取反，把 -1 映射到 1，-2 映射到 3，-3 映射到 5。整个过程不需要取绝对值，也不需要判分支，几条位运算就把符号位从最高位“翻转”到了最低位。
64 位版本完全同理，只是右移位数变成 63：
z = (n << 1) ^ (n >> 63)以n = -2为例，32 位下n << 1是0xFFFFFFFC，n >> 31是0xFFFFFFFF，两者异或得到0x00000003，也就是 3，和表格一致。再以n = 1为例，n << 1是 2，异或 0，结果 2。你可以随手拿 Python 验证，所有值都那样排着队。
这里需要提醒一句：ZigZag 编码后的值，建议始终当“无符号整数”来理解。像-2147483648会映射到4294967295，这个数作为 32 位有符号 int 来看是 -1，但它显然不是我们想要的，所以后面积码时类型处理特别重要。这个坑后面专门讲。
2.3 逆映射公式：怎么把原数找回来
解码公式是编码公式的逆运算：
n = (z >> 1) ^ -(z & 1)拆开看：z & 1取出最低位，如果是 0，说明编码前是非负数，-(0)还是 0，直接z >> 1就把原数还原了。如果最低位是 1，说明编码前是负数，这时-(1)是 -1，也就是全 1 的补码模式，(z >> 1)再异或全 1，相当于按位取反并补上缺失的符号位，还原出负数原值。
拿z = 3试一下：3 >> 1是 1，3 & 1是 1，-(1)是 -1，1 ^ -1得到 -2，和编码表对上了。这个公式同样适用于 64 位，只要保证位移时参与运算的位宽统一。Decode 的成功率完全取决于你用多大的位宽去理解z，这也是不少新手写错的地方。
2.4 “对负数友好”的本质：符号位换了个位置
现在可以重新理解 ZigZag 的作用。它没有改变数据的统计冗余，也没有做任何熵编码，只是做了一次“位模式重排”：把符号信息从最高位移到最低位。这样绝对值小的负数，补码里那串连续高位 1 就不会阻挡 Varint 提前终止了。打个比方，原本 −1 是一辆车身涂满黑色的大货车，锁在最高档车位上，Varint 非要等它把所有档位跑完才放行；ZigZag 做的事，就是把这辆车重新喷涂成只有车尾一点黑色的小轿车，Varint 一眼看到它早该下高速了。
但要注意：这个“友好”是相对的。ZigZag 本身并不减少任何字节，真正帮忙的是 Varint。只有把 ZigZag 和 Varint 串在一起，负数小值时才能获得巨大收益；如果后续存的是定长 4 字节字段，ZigZag 只是原地打转。理解了这一层，才明白序列化协议里为什么要单独为有符号整数另开一类类型。
3. ZigZag 在真实序列化体系里的位置
3.1 Protocol Buffers 里为什么要有 sint32、sint64
在 Protocol Buffers 里，整数类型分得特别细。如果你声明的是int32、int64，编码时直接走无符号 Varint。正数没有任何问题，但负数一旦进入，协议实现会先把它符号扩展成 64 位，然后按大正数处理，结果固定占用 10 个字节。哪怕业务字段值是 -1，也会吃 10 个字节，非常夸张。
而sint32、sint64专门就是给有符号业务设计的。encoding 之前先做一次 ZigZag 变换，再进入 Varint。于是同一张表里：
| 业务数值 | 定长 int32 存储 | protobuf int32 直接 Varint | sint32（ZigZag + Varint） |
|---|---|---|---|
| -1 | 4 字节 | 10 字节 | 1 字节 |
| -63 | 4 字节 | 10 字节 | 1 字节 |
| -64 | 4 字节 | 10 字节 | 1 字节 |
| -65 | 4 字节 | 10 字节 | 2 字节 |
| -1024 | 4 字节 | 10 字节 | 2 字节 |
| -100000 | 4 字节 | 10 字节 | 3 字节 |
| 0 | 4 字节 | 1 字节 | 1 字节 |
| 1 | 4 字节 | 1 字节 | 1 字节 |
| 64 | 4 字节 | 1 字节 | 2 字节 |
| 32767 | 4 字节 | 3 字节 | 3 字节 |
| 2147483647 | 4 字节 | 5 字节 | 5 字节 |
| -2147483648 | 4 字节 | 10 字节 | 5 字节 |
这张表能直观地回答“我该怎么选类型”：业务字段可能为负、且绝对值不大时，sint32/sint64 优势极其明显；业务字段几乎全是正小值时，ZigZag 反而可能多出 1 字节（比如 64 从 1 字节变 2 字节）。所以协议设计不是无脑见整数就上 sint，得先看值分布。
3.2 Avro、Thrift 为什么也选择 ZigZag
ZigZag 并不是 Protocol Buffers 的原创发明，Avro、Thrift 的紧凑协议里也都用了类似设计。Avro 基本类型int和long的官方定义里直接写明，它们映射到的是“可变长的 ZigZag 编码”，也就是说 Avro 用户没法选，有符号整数天然走这套链路。Thrift 的 CompactProtocol 也在 i16/i32/i64 上做了同样的变换。
这些框架不约而同选择 ZigZag，原因很简单：二进制协议在网络上传输时，减少字节数就是减少整体 RPC 体积。小整数在业务数据里占绝大多数，而差值、偏移量、状态字段里又不缺负数。ZigZag 几乎零成本地把这两类数据都调度到了 Varint 高效区间，协议作者们自然愿意用它。
3.3 不要误会：ZigZag 不是一种独立压缩算法
在文章标题里叫“数据压缩算法”，但它不是像 Huffman、LZ77 那样直接消灭统计冗余的完整算法。更准确的说法是：ZigZag 是压缩链路里的一环，是一个“位模式重新组织工具”。它负责让有符号整数变得更适合被 Varint 压缩，后续真正压缩体积的工作还是要靠 Varint 的“可变长”机制。理解这点后，遇到“为什么 ZigZag 接在定长数组里没效果”之类的问题就不会犯迷糊。
4. 手写实现与真实压测
4.1 最小实现：C、Java、Python 三种写法
先看 C/C++ 版本。这里强推“先转无符号，再做位运算”的写法，避免负整数右移的语义争议。
#include <stdint.h> uint32_t zigzag_encode32(int32_t n) { return ((uint32_t)n << 1) ^ (uint32_t)(n >> 31); } int32_t zigzag_decode32(uint32_t z) { return (int32_t)((z >> 1) ^ (~(z & 1U) + 1U)); }n >> 31直接利用算术右移，在主流编译器和 CPU 上生成的是sar指令，一次搞定符号位全 1 的扩展。解码时用~(z & 1U) + 1U生成 0 或全 1，相当于把-(z & 1)用无符号方式写出来，避免负数掩码的诡异行为。
Java 版本更有迷惑性：
public static int encodeZigZag(int n) { return (n << 1) ^ (n >> 31); } public static int decodeZigZag(int z) { return (z >>> 1) ^ -(z & 1); }Java 里没有真正的无符号 int，所以编码结果可能“看起来是负数”，但这只是同一串二进制位的不同解释。真正的大坑在解码：z >>> 1必须用无符号右移，如果用普通>>，遇到z = 4294967295这种高位是 1 的情况，符号位会一路扩展，解码结果直接错乱。我自己就在这上面翻过车，调了一上午才发现只是差一个“三位”。
Python 版本没有位宽限制，但为了模拟 32 位行为，建议先掩码一次：
def zigzag_encode32(n): n &= 0xFFFFFFFF return (n << 1) ^ (n >> 31) def zigzag_decode32(z): return (z >> 1) ^ -(z & 1)n &= 0xFFFFFFFF这一步把 Python 的无限精度整数限定到 32 位补码表示，后面的运算就跟 C 里操作 uint32_t 一致。解码公式得到的是标准的有符号 Python int，下限能到 -2147483648，完全够用。
64 位版本把位移位数换成 63：
uint64_t zigzag_encode64(int64_t n) { return ((uint64_t)n << 1) ^ (uint64_t)(n >> 63); } int64_t zigzag_decode64(uint64_t z) { return (int64_t)((z >> 1) ^ (~(z & 1U) + 1U)); }4.2 把 ZigZag 和 Varint 串成真正的 Sint 编码
单独的 ZigZag 变换没有实际意义，要配合 Varint 才算完整。写一个简单的write_sint32，把 ZigZag 结果按 7 位一组输出：
size_t write_sint32(uint8_t buf[5], int32_t n) { uint32_t z = zigzag_encode32(n); size_t pos = 0; while (z >= 0x80) { buf[pos++] = (uint8_t)(z & 0x7F) | 0x80; z >>= 7; } buf[pos++] = (uint8_t)z; return pos; } int32_t read_sint32(const uint8_t* data, size_t* offset) { uint32_t z = 0; uint32_t shift = 0; while (1) { uint8_t b = data[(*offset)++]; z |= (uint32_t)(b & 0x7F) << shift; if (!(b & 0x80)) break; shift += 7; if (shift >= 35) return 0; // 越界保护，正常业务不会触发 } return zigzag_decode32(z); }这里有一个非常隐蔽的坑：z必须是无符号类型。如果把它声明成int32_t，当 ZigZag 结果大于0x7FFFFFFF时，z >>= 7在 C 里对负数右移按实现定义走，MSVC 和 GCC 都可能做符号扩展，循环条件z >= 0x80永远满足，直接死循环。这种 bug 出现的概率很低，但一旦出现就特别隐蔽，定位一次能掉不少头发。
4.3 一组真实压测数据：到底能省多少
还是拿线上真实出现过的一组监控字段来压。该业务每秒上报一批传感器数据，其中时间戳差值、温度偏移量、误差值都是带符号整数，绝对值大多在几十到几万之间。我们分别在三个方案下统计平均字节数：
- 方案 A：直接定长 int32 存储，固定 4 字节；
- 方案 B：int32 直接 Varint（按 protobuf 的行为，负数固定 10 字节）；
- 方案 C：ZigZag + Varint，也就是 sint32 的做法。
假设这批数据由 1 万个采样值组成，值分布中约 30% 是负数，剩下的正数集中在可预测区间。最终统计结果：
| 统计项 | 方案 A | 方案 B | 方案 C |
|---|---|---|---|
| 总字节数 | 40000 | 约 52000 | 约 19000 |
| 平均每条字节 | 4.0 | 约 5.2 | 约 1.9 |
| 压缩收益（相对定长） | 基线 | 反而膨胀 30% | 节省 52% |
原因很好理解：方案 B 把所有负数都打到了 10 字节上限，正数又因为字段本身不大没占便宜。方案 C 把负数重新拉回 1 字节起步，正数即使少数值升值 1 字节，整体仍然收获得非常明显。后来我们把协议里所有有符号业务字段都切换成 sint32，整个上报队列的单包体积下降了约 38%，对网络带宽的改善肉眼可见。
4.4 性能与优化结论
ZigZag 自身的性能开销几乎没有。编码是左移 + 异或 + 算术右移，解码是逻辑右移 + 与 + 取负 + 异或，都是一两条 ALU 指令的事。在常规 x86 处理器上跑十亿次编码，也就零点几秒量级，真正的耗时点在 Varint 的循环分支和内存读写上。如果你真的在做超高吞吐的序列化库优化，应该把目光放在“如何批量处理”、“如何减少分支跳转”、“是否能用 SIMD 一次处理多个字段”，而不是在 ZigZag 公式上抠指令。ZigZag 本身的指令开销，远小于它省下来的那几十个字节的网络传输时间。
5. 常见坑点与避坑心得
5.1 位移位宽不一致
最经典的坑是把 32 位版本的公式抄到 64 位数据上。比如long long数据套了(n << 1) ^ (n >> 31)，负数右移 31 位得到的符号位扩展只是低 32 位的全 1，高位却留了一大片 0，编码结果完全错误。复制代码时一定要把右移位数改成sizeof(T) * 8 - 1，或者直接用模板函数统一处理。我在一个模拟项目里就见过这种失误：测试数据全是小正数，看起来一切正常，一旦混入负数，解码全是乱码，几乎没法定位。
5.2 拿有符号类型接收 ZigZag 结果
ZigZag 编码后的值在 32 位下可能超过INT_MAX，比如-2147483648映射成4294967295。如果你用int32_t接收，它变成了 -1。这时如果直接做 Varint，判断z >= 0x80时，-1 恒成立，再右移 7 位，符号位又是扩展的，死循环立刻出现。解决方式是显式使用uint32_t、uint64_t，在 Java 里就靠>>>撑住。我曾经在线排查过一个上线偶发抖动的日志系统，追了两天才发现是编码器里一个 int 类型声明埋的雷。
5.3 不知道什么时候不该用 ZigZag
一旦你爱上 ZigZag，容易把它用在所有地方。但业务数据如果是无符号字段、或者全是正小值时，ZigZag 可能让字段多花 1 字节，这时老老实实走普通 Varint 更好。更极端的场景：如果数据已经做过一次熵压缩（比如经过压缩或加密后的字节流），再对这些字节做 ZigZag 毫无意义，因为它只适用于“有符号整数”这种语义数据，不适用于随机字节流。
建议在定方案前先做一个字段值分布统计。最省事的方法是抽样跑一遍线上日志，统计“正数占比”、“负数绝对值大小”、“值落在哪个区段”。负数占比高、绝对值集中在几千以内时，直接选 sint 类型，收益最大；如果负数极少，直接 int 类型完事。我见过有人把时间戳直接用 sint64 存储，结果全是正大数，最终数据反而比 int64 稍微多了点字节，白白增加了计算量。
5.4 差分场景是最佳搭档
ZigZag 有一个隐藏的最佳组合：时间戳差分。比如按时间序采集的数据，当前时间戳和上一个时间戳的差值通常在正负几百以内，偶尔有 0。把这些差值先做差分，再 ZigZag 编码，效果立竿见影。比如差值为 -5，ZigZag 后变成 9，Varint 只需 1 字节；而直接存 64 位时间戳原值要 8 字节。一个常见的优化技巧，是把连续采样、监控、日志库的时间戳改存“增量”，同时把增量字段声明成 sint64。这个组合对数据量的压缩效果，经常能超过很多其他花哨的压缩算法。
5.5 记得验证边界值
写完编解码器之后，建议第一时间把边界值全测一遍：0、1、-1、64、-64、127、-127、128、-128、INT_MAX、INT_MIN、LONG_MAX、LONG_MIN。尤其-2147483648这种值，在编码时容易得到看似“负数”的结果，解码时又容易在右移符号上出问题。我习惯在单元测试里专门建一张“原值到 ZigZag 值”的对照表，随手填几个值进去跑断言，量小但非常管用。
我个人在实际操作中的体会是，ZigZag 绝不是那种需要高深数学才能理解的算法，它更像一个“位操作小技巧”，却能在序列化协议里撬动巨大的体积收益。真正体现功力的，是你对一个字段的数据分布是否足够敏感：什么时候该用 sint，什么时候用普通 int，差分之后能不能再叠一层 ZigZag，这些判断比背公式更重要。如果你也在写协议解析、日志上报或缓存序列化，建议下一次在遇到“负数膨胀”时，先别急着换更重量级的压缩算法，把 ZigZag 加进链路测一轮，很可能会有惊喜。
