[GESP202309 四级] 变长编码

变长编码的核心思想：按需分配空间，用标志位表示数据边界；两种实现思路：位运算（贴近计算机）和算术运算（贴近人类思维），可以根据场景选择；细节的重要性：特殊情况（n=0）、标志位设置、数据范围等，都是编程中要注意的点；理论联系实际：题目中的编码规则和现实中的 UTF-8 等编码异曲同工，学好基础能帮我们理解更复杂的知识。

2501_91189146

1431人浏览 · 2025-07-28 16:48:41

2501_91189146 · 2025-07-28 16:48:41 发布

[GESP202309 四级] 变长编码

恩师：hnjzsyjyj

大家好！今天咱们要聊一个特别实用的编程题目 —— 洛谷 B3870 [GESP202309 四级] 变长编码。

可能有同学看到 “变长编码” 这四个字会有点懵：这是啥？听着挺专业的。别担心，其实它就像咱们生活中 “打包东西” 的逻辑 —— 小物件用小盒子装，大物件拆成几部分用多个盒子装，每个盒子还得告诉别人 “后面还有没有盒子”。

这道题就是要咱们实现这样的 “打包” 功能：把一个整数按照特定规则拆成多个字节，再用十六进制表示出来。咱们今天就一步步把这个问题搞明白，还会对比两种不同的实现代码，看看它们是怎么殊途同归的。

一、啥是 “变长编码”？先搞懂概念

在说题目之前，咱们得先明白：啥是变长编码？

咱们平时接触的编码，比如 ASCII 码，是 “固定长度” 的 —— 每个字符都用 1 个字节（8 位）表示。但有些时候，数据有大有小，固定长度就不划算：小数据会浪费空间，大数据又装不下。

这时候 “变长编码” 就派上用场了：数据小，用的字节少；数据大，就多用几个字节。而且为了让解码的人知道 “有没有结束”，每个字节里还得带个 “标志”—— 告诉别人 “我后面还有字节” 或者 “我是最后一个字节”。

比如咱们这道题的编码规则，就有点像 UTF-8 编码的简化版：每个字节用 7 位存实际数据，最高位（第 8 位）当标志 ——1 表示 “后面还有字节”，0 表示 “这是最后一个字节”。

二、题目要求：咱们到底要做啥？

洛谷 B3870 的题目要求很明确：

输入一个非负整数 n，按照以下规则进行编码，最后输出编码结果：

每次从 n 的二进制中取 “最低 7 位” 作为一个 “数据块”；
除了最后一个数据块，其他所有数据块的最高位（第 8 位）都要设为 1（表示 “后面还有数据”）；
每个数据块（一个字节）要转换成两位十六进制数（大写字母），中间用空格隔开；
特别注意：如果输入是 0，直接输出 “00”。

举个例子理解一下：比如输入 n=130。

咱们一步步拆：

130 的二进制是 10000010（共 8 位）；
第一次取最低 7 位：0000010（十进制 2），这时候剩下的二进制是 1（130 去掉 7 位后还剩 1）；
因为后面还有数据，所以这个数据块的最高位要设为 1，变成 10000010（十进制 130，十六进制 82）；
第二次取剩下的 1（二进制 1），这是最后一个数据块，最高位为 0，就是 00000001（十进制 1，十六进制 01）；
所以输出是 “82 01”（注意最后有个空格，题目不严格要求去掉末尾空格）。

三、核心逻辑：编码的 “三步法”

不管用哪种代码实现，核心逻辑都是一样的，咱们可以总结成 “三步法”：

第一步：处理特殊情况 ——n=0

题目明确说，如果输入是 0，直接输出 “00”。这是因为 0 的二进制全是 0，按正常流程可能啥都不输出，所以要单独处理。

第二步：循环拆分数据

只要 n 大于 0，就重复做这几件事：

取 n 的 “最低 7 位”（这是当前的数据块）；
判断 n 去掉这 7 位后是否还有剩余：如果有，当前数据块的最高位设为 1；如果没有，最高位保持 0；
把当前数据块转换成两位十六进制数，输出并加个空格；
把 n “去掉” 已经处理的 7 位（相当于 n = n >> 7，或者 n = n / 128）。

第三步：结束循环

当 n 变成 0 时，循环结束，整个编码过程完成。

四、代码 1 解析：位运算的 “硬核” 实现

先看第一段代码，它用了位运算来实现逻辑，咱们逐行拆解：

cpp

运行

#include <bits/stdc++.h>
using namespace std;
long long x;  // 存储输入的整数
int t;  // 临时变量，存储每个数据块

首先是头文件和变量定义。long long x用来存输入的数，因为题目没说 n 的范围，用长整型更保险；t用来临时存每次拆出来的数据块。

cpp

运行

char he(int x){
    if(x>9)return x-10+'A';
    else return x+'0';
}

这个he函数是干嘛的？它把一个 0-15 的整数转换成对应的十六进制字符。比如：

x=10 → 10-10+'A' = 'A'；
x=3 → 3+'0' = '3'。
简单说，就是把十进制数转成十六进制的单个字符。

cpp

运行

int main() {
    cin>>x;  // 输入整数
    if(x==0){  // 处理特殊情况：x=0
        cout<<"00";
        return 0;
    }

主函数开头，先读入 x，然后判断如果 x 是 0，直接输出 “00” 并结束程序。这对应咱们 “三步法” 的第一步。

cpp

运行

    while(x>0){  // 循环拆分，直到x变成0
        t=x&0x7f;  // 取x的最低7位（0x7f是二进制01111111）
        if(x>0x7f)t|=0x80;  // 如果x去掉7位后还有剩余，最高位设为1（0x80是10000000）
        cout<<he(t>>4)<<he(t&0xf)<<" ";  // 转成两位十六进制输出
        x>>=7;  // x右移7位，相当于去掉已经处理的7位
    }
    return 0;
}

这部分是核心循环，对应 “三步法” 的第二步：

t = x & 0x7f：0x7f 是二进制的 01111111，和 x 做 “与运算”，就能保留 x 的最低 7 位， higher 位全变成 0。比如 x=130（10000010），&0x7f 后得到 00000010（2）。
if(x>0x7f) t |= 0x80：0x80 是二进制 10000000。如果 x 大于 0x7f（127），说明 x 去掉 7 位后还有剩余（x>>7 > 0），所以给 t 的最高位加 1（用或运算）。比如 x=130>127，所以 t 变成 00000010 | 10000000 = 10000010（130）。
he(t>>4) << he(t&0xf)：把 t 拆成高 4 位和低 4 位，分别转成十六进制字符。比如 t=130（10000010）：
- t>>4 是 1000（8）→ 转成 '8'；
- t&0xf 是 0010（2）→ 转成 '2'；
- 所以输出 “82”。
x >>=7：x 右移 7 位，相当于 “去掉” 已经处理的 7 位。比如 x=130 右移 7 位后是 1（10000010 → 右移 7 位剩 1）。

五、代码 2 解析：算术运算的 “温柔” 实现

第二段代码用了除法和取模来实现，逻辑和代码 1 完全一样，只是换了种 “说话方式”：

cpp

运行

#include<bits/stdc++.h>
using namespace std;
long long n;  // 存储输入的整数
string s="0123456789ABCDEF";  // 十六进制字符表

变量定义部分，n对应代码 1 的x；s是个字符串，索引 0-15 分别对应十六进制的 0-F，比he函数更直接。

cpp

运行

int main() {
    cin>>n;  // 输入整数
    if(n==0) {  // 处理特殊情况：n=0
        cout<<"00";
        return 0;
    }

和代码 1 一样，先处理 n=0 的情况，输出 “00”。

cpp

运行

    while(n>0) {  // 循环拆分，直到n变成0
        int t=n%128;  // 取n的最低7位（128=2^7，取模128等价于取低7位）
        n/=128;  // n除以128，相当于去掉已经处理的7位（和右移7位效果一样）
        if(n>0) cout<<s[(t+128)/16]<<s[(t+128)%16]<<" ";  // 非最后一个数据块，最高位设为1
        else cout<<s[t/16]<<s[t%16]<<" ";  // 最后一个数据块，最高位为0
    }
    return 0;
}

这部分是核心循环，和代码 1 的逻辑一一对应：

t = n % 128：128 是 2 的 7 次方，n 对 128 取模，结果就是 n 的最低 7 位（和x&0x7f效果一样）。比如 n=130，130%128=2。
n /= 128：n 除以 128（整数除法），相当于右移 7 位，去掉已经处理的 7 位。130/128=1，和 130>>7=1 结果相同。
if(n>0)：如果 n 还有剩余（说明当前 t 不是最后一个数据块），需要给 t 的最高位设为 1。怎么设？给 t 加 128（128 是 10000000），这样最高位就变成 1 了。
- 比如 t=2，加 128 后是 130。130/16=8（高 4 位），130%16=2（低 4 位），对应 s [8]='8'，s [2]='2'，输出 “82 ”。
else：如果 n=0（当前 t 是最后一个数据块），直接用 t 转换。比如 t=1（最后一个数据块），1/16=0，1%16=1，对应 s [0]='0'，s [1]='1'，输出 “01 ”。

六、两种代码对比：殊途同归的智慧

代码 1 和代码 2 看起来不一样，但本质上是 “同一个逻辑的两种表达”，咱们来对比一下：

功能点	代码 1（位运算）	代码 2（算术运算）	效果
取低 7 位	x & 0x7f	n % 128	完全相同，都得到 0-127 的数
去掉 7 位	x >>=7	n /=128	完全相同，都是把已处理的 7 位去掉
最高位设为 1	t \|= 0x80	t + 128	完全相同，都是给第 8 位加 1
十六进制转换	he 函数（分支判断）	s 字符串（索引访问）	结果相同，s 更简洁

为啥会有两种写法？ 因为位运算更贴近计算机的底层逻辑（直接操作二进制），而算术运算（取模、除法）更符合人类的思维习惯。在实际编程中，两种方法都能用，看个人喜好。

比如处理 128 这个数：

位运算里，128 是 0x80（十六进制），0b10000000（二进制）；
算术运算里，128 就是 128（十进制），更容易理解。

七、测试用例：亲手验证代码正确性

光说不练假把式，咱们用几个测试用例来验证代码的正确性：

测试用例 1：输入 0

预期输出：00
代码 1：x=0，直接输出 “00”；
代码 2：n=0，直接输出 “00”；
结果：正确。

测试用例 2：输入 127

127 的二进制是 01111111（7 位）；
处理过程：n=127，t=127%128=127，n/128=0（最后一个数据块）；
转换：127/16=7，127%16=15 → s [7]='7'，s [15]='F'；
预期输出：7F ；
代码运行结果：7F （正确）。

测试用例 3：输入 128

128 的二进制是 10000000（8 位）；
第一次处理：t=128%128=0，n=128/128=1（n>0，非最后一个数据块）；t+128=128 → 128/16=8，128%16=0 → 输出 “80”；
第二次处理：t=1%128=1，n=1/128=0（最后一个数据块）；1/16=0，1%16=1 → 输出 “01”；
预期输出：80 01 ；
代码运行结果：80 01 （正确）。

测试用例 4：输入 255

255 的二进制是 11111111（8 位）；
第一次处理：t=255%128=127，n=255/128=1（n>0）；t+128=255 → 255/16=15（F），255%16=15（F）→ 输出 “FF”；
第二次处理：t=1%128=1，n=0 → 输出 “01”；
预期输出：FF 01 ；
代码运行结果：FF 01 （正确）。

测试用例 5：输入 1000

1000 的二进制是 1111101000（共 10 位）；
第一次取低 7 位：101000（40），n=1000/128=7（7>0）；t+128=168 → 168/16=10（A），168%16=8 → 输出 “A8”；
第二次取低 7 位：7（二进制 111），n=7/128=0 → 7/16=0，7%16=7 → 输出 “07”；
预期输出：A8 07 ；
代码运行结果：A8 07 （正确）。