GESP四级真题B3870变长编码解析：从位运算到LEB128/varint

B3870 这道GESP202309 四级真题“变长编码”，我是被自己的第一个朴素写法坑惨之后，才去找“膜拜版”代码来参悟的。题目本身不难，就是给一个非负整数，按每7位一组拆开，变成若干带延续位的字节输出。但越是这种规则简单的题，越考对二进制位操作和输出格式的细腻程度。这篇文章我会把题面规则、样例推导、位运算原理、精简写法，以及我实际提交时踩过的坑全部摊开讲，适合正在备考GESP四级的人，也适合任何一个想把手糊位运算练扎实的刷题人。

1. 变长编码题面还原：7位一组、延续位与输出顺序

在没有看官方题解之前，我第一反应是“这不就是十六进制转换吗”？结果样例都过不了。先把规则一条条拆开，你会发现它其实是一个很工整的二进制切分游戏。

1.1 从低位开始，每7位切成一段

题面大概意思是：给定一个非负整数n，把它写成二进制形式，从最低位开始向左数，每7个二进制位切成一组，直到把所有的位都切完。注意是最低位先切，不是最高位先切。比如128的二进制是10000000，低7位是0000000，剩余的1另成一组；255的二进制是11111111，低7位是1111111，剩余的1再成一组。这种切法本身就是“小端”视角：先处理低位，再处理高位。

为什么偏偏是7位而不是8位？这算是整道题的核心。一个字节有8位，其中最高位被征用为“指示位”，剩下的7位才能真正放数据。换句话说，变长编码里每一个字节最大只能表示0到127之间的数。128以上的数，就必须拆成多个字节，每个字节带着自己那一小段7位数据，一个接一个排下去。

1.2 给每组加上“还有后续”标记

每一组7位数据都要放进一个字节的低7位，字节的最高位用来表示“后面还有没有下一组”。如果这一组不是最高位所在的组，说明后续还有数据，最高位就填1；如果这一组已经是最后一组，最高位填0。这个标志位叫延续位（continuation bit）。以128为例，低组7位全是0，且后面还有一组，所以低组字节变成10000000，也就是0x80；高组数据是1，且是最后一组，所以字节是00000001，也就是0x01。

这里可以理解成一个七层的抽屉柜子：每个字节是柜子的一层，低7位是抽屉里真正放的货物，最高位则是柜子侧面贴的标签，写着“楼上还有货”或“这是最顶层”。解码的人从最底层开始看，如果标签写“楼上还有货”，就继续往上走；写“顶层”，就可以清点货物了。

1.3 按低位到高位的顺序输出十六进制

题目要求输出时按“从低位组到高位组”的顺序，每个字节转成两位大写十六进制，并用一个空格隔开。所以128输出“80 01”，而不是“01 80”。这与我们平常书写二进制时从高位到低位的习惯相反，但解码时从左往右读非常自然：读到最高位是1的字节，就知道后面还跟着字节；读到最高位是0的字节，就结束了。

下面是几个标准样例的推导，直接用位分组表示：

其中0比较特殊，它没有任何非零位，但按照规则仍然输出“00”，表示“零这个数也要编码成一个字节”。这个特殊点在后面写代码时是个非常重要的边界条件，稍不留神就会在这里翻车。

2. 为什么选择7位：延续位、字节序与可读性背后的设计逻辑

单纯背规则容易忘，理解为什么这样设计，以后碰见类似编码才不会慌。这题表面上是模拟题，背后其实是数据压缩里很经典的“基128变长编码”思想。

2.1 一个字节只有8位，最高位必须让给控制信息

如果所有8位都用来表示数据，一个字节最多表示255，遇到更大的数只能借助额外信息告诉解码器“这个数还没完”。所以必须从8位里拿出一位来表示“是否继续”。剩下的7位就是真正的数据位。7位的范围是0到127，编码0~127的数时只需要一个字节；128以上的数才需要多个字节。对很多应用来说，小整数出现频率极高，这种设计能显著节省空间。

举一个直观对比：如果用固定4字节整数，数字0也要占满32位；但用变长编码，0只占一个字节，也就是8位。当大量数据都是小整数时，这种编码能把存储体积压缩到原来的四分之一甚至更少。这也是为什么它能在各种序列化协议里活到今天。

2.2 延续位放在最高位，目的是让解码器顺序扫描

延续位放在每个字节的最高位而不是最低位，是为了让解码程序拿到一个字节后，立刻可以判断是继续读下一个还是结束。如果把延续位放在最低位，解码时需要先做移位才能判断，多一步操作。放在最高位之后，解码逻辑可以写成：

unsigned result = 0; int shift = 0; int b; do { b = getchar(); result |= (unsigned)(b & 0x7F) << shift; shift += 7; } while (b & 0x80);

读一个字节，取出低7位，移到对应位置，再检查最高位。整个过程从左到右一次扫描，不需要倒序，非常符合流式解码的直觉。这也是为什么编码时要把低7位组先输出，而不是像传统书写那样把高位放在前面。

2.3 十六进制输出其实是在替我们检查二进制

也许有人会问，为什么不直接输出01000000这种二进制串？因为太长且容易看错。一个字节正好对应两位十六进制：高4位一位，低4位一位。题目让用两位大写十六进制输出，本质上是把8位二进制压缩成2个可读字符。换句话，输出“80”就是在输出字节10000000。使用十六进制能方便人工核对分组和延续位，这也是考试题喜欢用十六进制作为输出格式的原因。

3. 核心位运算拆解：取低7位、右移、加延续位的组合拳

现在进入代码层面的核心。所有变长编码程序的核心，无非三件事：取出当前最低7位、移到下一组、判断是否还有后续。分别对应三个位运算。

3.1 n & 0x7F：取出最低7位

0x7F是十六进制，二进制是01111111，正好是低7位全1、最高位0的掩码。n & 0x7F会保留n的最低7位，把更高位全部清零。例如n=128，二进制10000000，按位与01111111，结果是00000000，也就是0。这步相当于把当前这一组7位从整个整数里单独抠出来。

有的初学者会想，为什么不直接n % 128？其实也可以，因为0x7F等于127，按位与n & 127和取余n % 128在正数范围内效果一样。但位运算更快，而且可以清楚表达“我要的是最低7位的二进制位”。在竞赛代码里，位运算读起来也更专业。

3.2 n >>= 7：把下一组移动到最低位

右移7位，意味着把刚才处理完的7位从n里移除，原来第8位及以上的位整体向右移动，原本的高一组现在变成了最低7位。比如n=128经过n>>=7后变成1。这一步必须放在“取出低7位”之后，否则会丢失数据。循环继续时，下一组的7位已经在最低位，直接重复n & 0x7F就能继续取出。

可以类比成切蛋糕：第一刀先切下最右边一块，然后把剩下的蛋糕整体往右推，让下一块跑到最右边，方便再切。循环往复，直到整块蛋糕切完。

3.3 根据是否还有剩余来决定是否置最高位

取出低7位后，我们要看n右移后是不是0。如果不为0，说明后面还有更高位的组没处理完，当前字节的最高位要置1；如果右移后为0，说明所有位都已经处理完，当前字节最高位保持0。实现时用if (n > 0) b |= 0x80;或者更紧凑的b | (n ? 0x80 : 0)。0x80的二进制是10000000，按位或可以把最高位置成1，同时不影响低7位。

这里稍微展开讲一个容易困惑的点：我们判断的是“右移之后的n”，不是右移之前的n。因为右移之后的n如果非0，说明还有更高位的数据；如果只看右移之前的n，128右移前非0，但这不代表后面还有数据，因为当前组始终存在。所以必须先用完当前组，再判断剩余量。

3.4 do-while结构保证至少输出一个字节

对于n=0，如果不进入循环，输出就是空的，这不符合要求。所以循环采用do { ... } while (n != 0);，无论n是否为0，都先执行一次循环体。第一次循环会输出00，然后n右移后仍然是0，循环结束。这样零值也有编码结果。

4. 膜拜版代码：从数组实现到一行printf的精简之路

我最初写的是先算出所有字节存进数组，最后再统一输出的版本，逻辑清楚但代码不短。后来看到别人的“膜拜版”，是在循环里一边算一边输出，还用printf的格式串控制空格，省掉了整个数组和多余变量。下面把两条路都写出来，你可以对比着看。

4.1 先算后输的数组版

#include <cstdio> int main() { unsigned n; scanf("%u", &n); unsigned char bytes[10]; int cnt = 0; do { unsigned char b = n & 0x7F; n >>= 7; if (n > 0) b |= 0x80; bytes[cnt++] = b; } while (n > 0); for (int i = 0; i < cnt; i++) { if (i > 0) putchar(' '); printf("%02X", bytes[i]); } return 0; }

这个版本很好懂，bytes数组用于暂存每个字节，最后统一打印。%02X自动补齐两位大写十六进制。数组大小为10，是因为无符号32位整数最多需要5个字节（32除以7向上取整是5），64位最大需要10个字节，所以10足够。考试中如果保险起见，可以开到15。

4.2 边算边输出的膜拜版

#include <cstdio> int main() { unsigned n; scanf("%u", &n); do { int b = n & 0x7F; n >>= 7; printf("%02X%s", b | (n ? 0x80 : 0), n ? " " : ""); } while (n); return 0; }

这个版本最让我膜拜的地方是printf("%02X%s", b | (n ? 0x80 : 0), n ? " " : "")的写法。printf从右往左处理参数，第二个格式符%s接受一个空字符串或一个空格字符串。当n右移后还不为0，说明当前字节不是最后一个，于是追加一个空格；当n为0，说明当前字节是最后一个，追加空字符串。这样既没有前导空格，也不会在末尾留下多余空格。

我们模拟一次n=128的执行：

• 第一次循环：b=0，n右移后=1，输出80（字节80加一个空格）；
• 第二次循环：b=1，n右移后=0，输出01；
• 结果80 01，完全正确。

对比数组版和膜拜版，数组版胜在逻辑直观，适合考试时快速写出不出错；膜拜版胜在代码简短，每个操作都是必须的存在，没有多余变量，适合在题解区“秀操作”。你可以先掌握数组版，再看懂膜拜版，考试时用哪个都行，只要能保证不写错。

4.3 Python参考实现

如果习惯用Python，同样思路可以这样写：

n = int(input().strip()) out = [] while True: b = n & 0x7F n >>= 7 if n: b |= 0x80 out.append(f"{b:02X}") if n == 0: break print(" ".join(out))

Python的整数是无限精度的，所以输入再大也不怕溢出，逻辑和C++完全一致。这个版本作为对照，能帮助你确认自己对规则的理解。

5. 提交前必须自查的四个坑：零值、空格、十六进制格式与类型选择

这题难不住思路清晰的人，但特别能坑细节不到位的人。我在第一次提交时就被输出格式坑了，反复看了三次评测结果才发现问题。下面这些坑每一个都值得记下来。

5.1 坑一：n=0时的空输出

如果你用while(n != 0)作为外层循环，那么n=0时一次循环体都不会执行，最终啥也不输出。样例里一定有0，所以会直接报错。解决方式就是改用do-while，或者单独判断if (n == 0)输出00。无论n是多少，至少要产生一个字节，这是变长编码的规则。

5.2 坑二：多余或缺失的空格

在OJ判题中，行末多一个空格通常也算错。最容易出的问题有两个：一是在每个字节后面都打空格，结果行尾多了一个；二是在第一个字节前面多打一个空格。用printf("%02X%s", ..., n ? " " : "")可以同时避免这两种问题，因为追加空格的时机是“当前字节后面还有字节”时，而判断依据是右移后的n是否为0。注意这个n必须在循环体内先右移，再在printf里使用，顺序不能反。

5.3 坑三：十六进制的大小写和补位

题目明确要求两个字符的大写十六进制，A~F必须大写。C语言的%X输出大写，%x输出小写，不要选错。同时需要用%02X而不是%X：如果不写02，小于0x10的字节会只输出一个字符，比如十进制的10会变成A，而正确结果应该是0A。02的意思是“最小宽度为2，不足补0”。

5.4 坑四：有符号数和算术右移问题

这里的整数非负，应该用无符号类型读取和计算。如果用了int n并且输入值很大，那么n >>= 7可能变成算术右移，右移时高位补符号位，导致负数永远不为0，循环无法结束；即使结果不是负数，不同编译器的行为也可能不一致。所以读入和存储都使用unsigned int，64位数据用unsigned long long。同时注意scanf的格式串用%u对应unsigned，不要用%d。

5.5 如何自查

写完后至少测这几组数据：0、1、127、128、255、256、65535。对照前文的表格验证结果。也可以写一个反向解码函数，把编码结果还原成原来的数，再用随机大整数来回验证。编码和解码互为逆过程，能自己写一遍解码，就说明真的理解了这个编码规则。

6. 从B3870到真实世界：LEB128、varint与UTF-8中的变长编码

很多人把这题当成单纯的“二进制分组”题，其实它背后是一整套工业界通用的变长编码思想。理解了这道题，等于顺手把几种经典编码的共同原理打通了。

6.1 LEB128与MIDI中的VLQ

LEB128（Little Endian Base 128）是DWARF调试信息等场景里常用的整数编码，规则和B3870几乎一模一样：从低位开始，每7位一组，每个字节最高位是延续位，最后一个字节的延续位为0。MIDI文件里的可变长度数量VLQ（Variable-Length Quantity）用的也是同一种思想，只不过数据组顺序不同。所以以后遇到LEB128，你直接可以套用这里的位运算思维。

6.2 Protocol Buffers的varint

Google的Protocol Buffers序列化格式中，整数用varint编码。它的规则是：每个字节低7位存数据，最高位1表示后续还有字节，0表示结束，按小端顺序输出。这与B3870完全同源。比如整数1，编码为0x01；整数300，编码为0xAC 0x02。如果你已经会做B3870，那么理解varint就是几分钟的事。

6.3 UTF-8中的连续字节标记

UTF-8用每个字节的最高位组合来区分一个字符有几个字节：首字节中连续1的个数表示后续字节数，后续字节统一用10开头。虽然具体规则不同，但“用字节中的部分位做控制信息，其余位做数据信息”的思路是一脉相承的。所以刷题时遇到的变长编码，并不只是考场上的冷门规则，而是很多真实格式的底层基石。

6.4 一个值得试试的扩展练习

我建议你在AC之后，再写一个解码程序：输入用空格分隔的若干两位十六进制字节，输出还原后的十进制整数。解码逻辑就是编码的逆过程：每个字节去掉最高位，取低7位，从低位到高位拼起来。写完后随机造几组数据，编码再解码，如果完全一致，这道题才算真正吃透。我个人在做完这个练习之后，再去看Protocol Buffers的二进制格式文档，基本是秒懂，因为里面的整数编码思想就是这题换了一层皮。