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的字节就结束了。下面是几个标准样例的推导直接用位分组表示输入nn的二进制从低到高按7位分组加延续位后的字节输出0000000000000000000110000001000000010112711111111111111011111117F128100000000000000、110000000、0000000180 01255111111111111111、111111111、00000001FF 012561000000000000000、1010000000、0000001080 02其中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位把更高位全部清零。例如n128二进制10000000按位与01111111结果是00000000也就是0。这步相当于把当前这一组7位从整个整数里单独抠出来。有的初学者会想为什么不直接n % 128其实也可以因为0x7F等于127按位与n 127和取余n % 128在正数范围内效果一样。但位运算更快而且可以清楚表达“我要的是最低7位的二进制位”。在竞赛代码里位运算读起来也更专业。3.2 n 7把下一组移动到最低位右移7位意味着把刚才处理完的7位从n里移除原来第8位及以上的位整体向右移动原本的高一组现在变成了最低7位。比如n128经过n7后变成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说明还有更高位的数据如果只看右移之前的n128右移前非0但这不代表后面还有数据因为当前组始终存在。所以必须先用完当前组再判断剩余量。3.4 do-while结构保证至少输出一个字节对于n0如果不进入循环输出就是空的这不符合要求。所以循环采用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向上取整是564位最大需要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说明当前字节是最后一个追加空字符串。这样既没有前导空格也不会在末尾留下多余空格。我们模拟一次n128的执行第一次循环b0n右移后1输出80字节80加一个空格第二次循环b1n右移后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 坑一n0时的空输出如果你用while(n ! 0)作为外层循环那么n0时一次循环体都不会执行最终啥也不输出。样例里一定有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 int64位数据用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中的VLQLEB128Little Endian Base 128是DWARF调试信息等场景里常用的整数编码规则和B3870几乎一模一样从低位开始每7位一组每个字节最高位是延续位最后一个字节的延续位为0。MIDI文件里的可变长度数量VLQVariable-Length Quantity用的也是同一种思想只不过数据组顺序不同。所以以后遇到LEB128你直接可以套用这里的位运算思维。6.2 Protocol Buffers的varintGoogle的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的二进制格式文档基本是秒懂因为里面的整数编码思想就是这题换了一层皮。