GESP 题解库 / 4 级题解 / [GESP202309 四级] 变长编码 · 第 18 / 25 题
GESP202309 四级 · B3870 · 简单

变长编码

把非负整数按 7 bit 分组编码,低位组带续位标志 1、最高位组带 0,输出十六进制字节。

📊
N ≤ 100
数据组数
🔢
非负整数
数值范围
⚡
O(位数)
时间复杂度
🎯
7 bit 分组 + 续位标志
核心算法
01
题目拆解
把题目拆成一块块,看清全貌

📝 题目原文

一种正整数的变长编码方式,规则如下:

  1. 把非负整数写成二进制形式,例如 (926)₁₀ = (1110011110)₂
  2. 从低位到高位每 7 bit 切一组,不足 7 bit 的高位补 0
  3. 由代表低位的组开始,给每组加一个最高位:最后一组(最高位组)补 0,其余组补 1

例:0 编码为 00000000(1 字节);926 编码为 10011110 和 00000111(2 字节)。

输出用两位大写十六进制表示每个字节,空格分隔。

💡
人话翻译:核心就是"按 7 位切块"。每个字节留出最高位当作"还有下一块吗"的标志位:还有就写 1,是最后一块就写 0。这样做的好处是:小数字只需 1 个字节,大数字可以扩展到多个字节。

🔍 关键词提取

位运算7 bit 分组续位标志十六进制输出

已知条件

项目说明
输入第一行 N;随后 N 行每行一个非负整数
输出每行一个变长编码,两位大写十六进制、空格分隔
数据范围N ≤ 100
数值范围非负整数(示例含 9 × 10¹⁷ 量级)
分组低位在前,每组 7 bit

需要解决的问题

02
思维导图
整理解题思路的全貌
🧬 按 7 bit 切块 + 续位标志
📥 读入
N 个非负整数
0 也要处理
大数用 long long
N ≤ 100
✂️ 切块
x & 0x7F 取低 7 位
x >>= 7 继续
每轮得一个组
x 变 0 时结束
🏷️ 加标志
先得到的组是低位组
非最后一组 | 0x80
最后一组不加标志
输出顺序:低位组在前
🖨️ 输出
每字节两位大写十六进制
字节间用空格分隔
0 输出 00
注意换行
03
样例手算推导
样例 926 的编码过程

🧮 926 的完整编码过程

926 的二进制是 1110011110(共 10 位)。

1
第 1 组:取低 7 位

926 & 0x7F = 926 mod 128

926 = 7 × 128 + 30,所以低 7 位是 30

30 的二进制是 0011110

这不是最后一组(因为右移后还不为 0)→ 补 1 → 10011110 = 0x9E

第 1 个字节:9E(低位组)

2
第 2 组:右移 7 位

926 >> 7 = 7

7 的二进制是 0000111(补足 7 位)

右移后 x = 7 >> 7 = 0 → 这是最后一组 → 补 0 → 00000111 = 0x07

第 2 个字节:07(最高位组)

3
拼接输出

低位组在前 → 输出顺序为 9E 然后 07

✅ 结果 "9E 07"

步骤x 的值x & 0x7F是否最后一组加标志后十六进制
第 1 组92630(0011110)否(右移后为 7 ≠ 0)100111109E
第 2 组77(0000111)是(右移后为 0)0000011107

输出:9E 07 ✓

🧮 几个特殊值

输入二进制分组情况编码结果
00只有一组(全 0)00
11一组 000000101
1271111111一组 1111111,是最后一组 → 011111117F
12810000000低 7 位 = 0,高位 = 1 → 两组80 01
9261110011110两组9E 07
1
重点看 0 和 127

0:切不出任何组(x 一开始就是 0)

按规则要输出一个全 0 字节 → 00

127:正好 7 位全是 1

它是唯一一组(也是最后一组)→ 最高位补 0 → 01111111 = 0x7F

✅ 特判 0 很关键

2
重点看 128

128 = 10000000(8 位)

低 7 位 = 0000000 = 0,不是最后一组 → 10000000 = 0x80

右移 7 位后 x = 1 → 是最后一组 → 0000001 = 0x01

✅ 输出 "80 01"

⚠️
0 必须特判:如果直接写 while (x > 0) 循环,x = 0 时一次都不执行,会输出空行。正确做法是先塞入一个 0 组,或者单独判断"若 x == 0 则输出 00"。
04
解法对比
位运算直接切分 vs 转成字符串处理

⚔️ 解法对比

🟢 位运算直接切分(推荐) 推荐

用 &0x7F 和 >>7 循环取出各组

  • 时间 O(组数)
  • 代码 10 行
  • 不需要字符串转换
  • 处理大数也轻松
💡
核心循环:while (true) { int g = x & 0x7F; x >>= 7; if (x) push(g | 0x80); else { push(g); break; } }——先取低位、再看是否还有,顺序天然正确。

🟠 先转二进制字符串再切

把数转成 01 串,按 7 位切分后加标志

  • 需要手写进制转换
  • 字符串拼接容易出错
  • 代码长一倍
  • 大数处理更麻烦
⚠️
结论:位运算直接表达了"取低 7 位"这个意图,是这类题的正解思路。转成字符串再切反而绕远路。

📈 性能对比

方案代码量大数友好度
位运算约 10 行高
字符串约 25 行中
05
算法流程图
循环取低 7 位并加续位标志
开始读入 N;对每个数 x 处理x == 0 吗?是 ✓直接输出 00否 ✗进入位运算循环循环:取 g = x & 0x7F,然后 x >>= 7x 是否已变成 0?是 ✓这是最后一组 → 输出 g否 ✗输出 g | 0x80(带续位)按顺序输出各字节(两位大写十六进制,空格分隔)结束x 还没到 0 → 继续取下一组
← 左右滑动查看完整流程图
06
动手算一算
自己输入数据试试看

🧬 变长编码器

每行输入一个非负整数,程序会展示 7 bit 分组过程与编码结果。

结果会显示在这里

点按钮开始 →

07
代码精讲
逐段拆解,彻底搞懂

💻 完整 C++ 代码

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    scanf("%d", &n);

    while (n--) {
        unsigned long long x;
        scanf("%llu", &x);

        vector<int> bytes;                  // 存放各字节(低位组在前)

        if (x == 0) {
            bytes.push_back(0);             // 0 特判:输出一个全 0 字节
        } else {
            while (true) {
                int g = x & 0x7F;           // 取低 7 位
                x >>= 7;                    // 右移 7 位
                if (x != 0) {
                    bytes.push_back(g | 0x80);   // 不是最后一组,最高位补 1
                } else {
                    bytes.push_back(g);          // 是最后一组,最高位补 0
                    break;
                }
            }
        }

        // 输出:两位大写十六进制,空格分隔
        for (int i = 0; i < (int)bytes.size(); i++) {
            if (i) printf(" ");
            printf("%02X", bytes[i]);
        }
        printf("\n");
    }
    return 0;
}
🔑
为什么用 while (true) 而不是 while (x > 0)?因为我们需要在取完最后一组之后再判断一次(用来决定最高位补 0 还是补 1)。如果写成 while (x > 0),就无法区分"当前组是不是最后一组"。while (true) + 内部 break 的写法让判断位置更自然。

📖 关键几行怎么看

代码作用为什么这样写
x & 0x7F取低 7 位0x7F = 0b1111111
x >>= 7右移 7 位把已处理的 7 位丢掉
g | 0x80补续位 10x80 = 0b10000000,置最高位
printf("%02X", ...)输出十六进制%02X 表示至少两位、不足补 0、大写
⚠️
三个坑:① 忘记特判 x == 0(会输出空行);② 输出顺序搞反(应该是低位组先输出);③ 用 %02x 小写输出(题目要求大写,用 %02X)。
08
边界测试 & 易错点
把坑都踩一遍,考试不翻车

🧪 边界测试用例表

写完程序后,用这些数据自查一遍:

输入答案考察点
000零值特判
101最小正整数
1277F恰好 7 位全 1,最高位补 0
12880 01刚好多出一位,需要两组
9269E 07题面样例
255FF 01八位全 1
✅
自查清单:① 0 处理了吗?② 低位组在前吗?③ 十六进制是大写吗?

🚨 易错点清单

⚠️
忘记特判 0:while (x > 0) 会让 0 输出空行,应输出 00。
⚠️
输出顺序错:应从低位组开始输出(先输出 9E 再输出 07)。
⚠️
大小写错:题目要求大写十六进制,C++ 用 %02X(大写的 X)。
09
复杂度分析
算算效率怎么样

📊 复杂度四宫格

时间复杂度
O(组数)
空间复杂度
O(组数)
每组
7 bit
组数
约 位数 / 7

时间怎么算的?

空间都用在哪?

需要保存各字节(最多 10 个)。

✅ 运算量极小,瞬间完成。这题考的是"位运算 + 续位标志"的编码思路,不是效率。

10
知识拓展
学一道题,会一类题

🔗 常用技巧小抄

// 位运算常用掩码
// 0x7F = 0b01111111   取低 7 位
// 0x80 = 0b10000000   置最高位为 1
// 0xFF = 0b11111111   一个字节

// 十六进制输出格式
printf("%02X", v);   // 至少 2 位、大写、不足补 0
printf("%02x", v);   // 小写版本
printf("%X", v);     // 不补 0

// 类似的"变长/前缀"编码思想
// - UTF-8:用字节高位的连续 1 的个数表示"这个字符占几个字节"
// - 7-bit 变长整数(protobuf varint):每字节低 7 位是数据、最高位是续位标志
// 本题就是 varint 编码!

🌟 举一反三

把这道题用到的基本功拆出来,它们能迁移到很多同类问题上。

能力点本题怎么用还能迁移到
掩码取位& 0x7F、>>= 7位运算、编码解码、状态压缩
续位标志最高位表示"还有下一块"varint、UTF-8 等变长编码
十六进制格式化%02X所有需要固定宽度十六进制输出的题
🌟
思考题:本题的编码其实就是工业界广泛使用的 varint(变长整数)编码(protobuf 就用它压缩整数)。如果给你一串编码后的字节,你能解码回原来的整数吗?(提示:从第一个字节开始,若最高位是 1 就继续读下一个字节,每读完一个字节就把它的低 7 位拼到结果的低位方向,直到遇到最高位为 0 的字节为止。这就是"编码的逆运算"。)