luogu-B3870 [GESP202309 四级] 变长编码

GESP C++四级2023年9月真题，函数、位运算等应用，难度⭐⭐★☆☆。个人认为23年GESP考试设立初期各级考试的题难度相对较高，本题在洛谷评定为普及-。

luogu-B3870 [GESP202309 四级] 变长编码

题目要求

题目描述

小明刚刚学习了三种整数编码方式：原码、反码、补码，并了解到计算机存储整数通常使用补码。但他总是觉得，生活中很少用到 $2^{31}-1$ 这么大的数，生活中常用的 $0 \sim 100$ 这种数也同样需要用 $4$ 个字节的补码表示，太浪费了些。热爱学习的小明通过搜索，发现了一种正整数的变长编码方式。这种编码方式的规则如下：
1.对于给定的正整数，首先将其表达为二进制形式。例如，
$>(0)_{\{10\}}=(0)_{\{2\}} >$
和
$>(926)_{\{10\}}=(1110011110)_{\{2\}} >$
2.将二进制数从低位到高位切分成每组 $7$ bit，不足 $7$ bit 的在高位用 $0$ 填补。例如，
$>(0)_{\{2\}} >$
变为 $0000000$ 的一组，
$>(1110011110)_{\{2\}} >$
变为 $0011110$ 和 $0000111$ 的两组。
3.由代表低位的组开始，为其加入最高位。如果这组是最后一组，则在最高位填上 $0$ ，否则在最高位填上 $1$ 。于是， $0$ 的变长编码为 $00000000$ 一个字节， $926$ 的变长编码为 $10011110$ 和 $00000111$ 两个字节。
这种编码方式可以用更少的字节表达比较小的数，也可以用很多的字节表达非常大的数。例如， $987654321012345678$ 的二进制为
$>(0001101 \ 1011010 \ 0110110 \ 1001011 \ 1110100 \ 0100110 \ 1001000 \ 0010110 \ 1001110)_{\{2\}} >$
，于是它的变长编码为（十六进制表示） CE 96 C8 A6 F4 CB B6 DA 0D，共 $9$ 个字节。
你能通过编写程序，找到一个正整数的变长编码吗？

输入格式

输入第一行，包含一个正整数 $N$ 。约定 $0\le N \le 10^{18}$ 。

输出格式

输出一行，输出 $N$ 对应的变长编码的每个字节，每个字节均以 $2$ 位十六进制表示（其中， A-F 使用大写字母表示），两个字节间以空格分隔。

输入输出样例 #1

输入 #1

输出 #1

输入输出样例 #2

输入 #2

输出 #2

9E 07

输入输出样例 #3

输入 #3

987654321012345678

输出 #3

CE 96 C8 A6 F4 CB B6 DA 0D

题目分析

本题主要考察了二进制转换、位运算和字符串处理的能力。这里提供两种解决思路，供参考：

方法一：二进制字符串处理

这种方法的思路比较直观，主要步骤如下：

先将输入的十进制数转换成二进制字符串
从低位到高位每7位进行分组，不足7位的用0补齐
根据是否为最后一组，在每组最高位添加0或1标识位
最后将每组二进制转换为十六进制输出

这种方法的优点是思路清晰，容易理解和实现。缺点是需要进行字符串处理，效率相对较低。

方法二：位运算处理

这种方法直接使用位运算进行处理，主要步骤如下：

使用位与运算(&)每次取出最低7位
根据是否还有后续数据，设置当前字节的最高位(通过位或运算|)
将原数右移7位，继续处理下一组数据
最后将每个字节转换为十六进制输出

这种方法的优点是运算效率高，不需要进行字符串转换。缺点是位运算的代码相对理解起来有难度。

算法复杂度分析

方法一：二进制字符串处理

时间复杂度: $O(\log n)$ $O (lo g n)$ ， $n$ $n$ 为正整数的值。
- 将十进制数转换为二进制字符串需要 $O(\log n)$ 次除法运算
- 字符串分组和处理需要遍历整个二进制字符串，长度为 $O(\log n)$
- 每组转换为十六进制输出是常数时间 $O(1)$
空间复杂度: $O(\log n)$ $O (lo g n)$
- 需要存储二进制字符串，长度为 $O(\log n)$
- 存储结果数组，大小为 $O(\log n / 7) \approx O(\log n)$

方法二：位运算处理

时间复杂度: $O(\log n)$ $O (lo g n)$
- 每次右移7位，总共需要 $O(\lfloor \log n / 7 \rfloor) \approx O(\log n)$ 次操作
- 每次位运算和十六进制转换是常数时间 $O(1)$
空间复杂度: $O(\log n)$ $O (lo g n)$
- 只需要存储结果数组，大小为 $O(\lfloor \log n / 7 \rfloor) \approx O(\log n)$

虽然两种方法的渐进复杂度相同，且能正确解决问题，但在实际应用中，建议尽量理解和使用方法二，因为其执行效率更高，且在处理大数据时更有优势。

{% include custom/custom-post-content-inner.html %}

示例代码

方法一：转换成二进制字符串处理（思维最直接）

下面示例代码可能不是最简洁，但是步骤比较清晰，容易理解，不跳步。

#include <algorithm>
#include <iomanip>
#include <iostream>
#include <string>
#include <vector>
#include <cstdio>

// 对整数n进行变长编码，返回编码后的字节序列
// 变长编码方式：每7位二进制为一组，最高位为1表示后续还有字节，最高位为0表示最后一个字节
std::vector<std::string> encode_variant(long long n) {
    std::vector<std::string> result;  // 存储编码结果
    if (n == 0) { // 特殊情况：n为0时，直接返回"00"
        result.push_back("00");
        return result;
    }
    // 将n转换为二进制字符串（高位在前，低位在后）
    std::string tmp;
    while (n != 0) {
        // 每次取最低位，拼接到tmp前面
        tmp = char(n % 2 + '0') + tmp;
        n /= 2;
    }

    int l_tmp = tmp.length(); // 二进制字符串长度

    if (l_tmp <= 7) {
        // 如果二进制长度不超过7位，直接补在后面，最高位为0，表示这是最后一个字节
        result.push_back('0' + tmp);
    } else {
        // 如果超过7位，需要分组处理
        int f_length = l_tmp % 7; // 头部不足7位的长度
        int idx = l_tmp - 7;      // 从倒数第7位开始分组
        // 从高位到低位，每7位为一组，最高位为1，表示后续还有字节
        while (idx >= 0) {
            std::string cur_str = tmp.substr(idx, 7); // 取7位
            result.push_back('1' + cur_str);          // 最高位为1
            idx -= 7;
        }
        // 如果有头部不足7位的部分，需要补0到7位，最高位为0，表示最后一个字节
        if (f_length != 0) {
            std::string tmp_str = tmp.substr(0, f_length); // 取头部不足7位
            // 补0到7位
            for (int j = 0; j < 7 - f_length; j++) {
                tmp_str = '0' + tmp_str;
            }
            result.push_back('0' + tmp_str); // 最高位为0
        }
    }

    return result;  // 返回编码后的字节序列
}

int main() {
    long long n;
    std::cin >> n;  // 从标准输入读取一个整数
    // 对输入的整数进行变长编码
    std::vector<std::string> result = encode_variant(n);

    // 以16进制格式输出编码结果，每个字节宽度为2，前导补0，大写字母
    for (std::string str : result) {
        // 将二进制字符串转为整数，再以16进制输出
        printf("%02X", stoll(str, nullptr, 2));
        std::cout << " ";
    }

    return 0;  // 程序结束
}

方法二：直接利用位运算取相应位的值（推荐）

#include <iostream>
#include <vector>
#include <algorithm>
#include <iomanip>

// 对整数n进行变长编码，返回编码后的字节序列
std::vector<long long> encode_variant(long long n) {
    std::vector<long long> result; // 存储编码结果
    if (n == 0) { // 特殊情况：n为0时，直接返回0
        result.push_back(0);
        return result;
    }
    // 当n不为0时，进行变长编码
    while (n != 0) {
        long long tmp = n & 0b1111111; // 取n的低7位
        n >>= 7; // n右移7位，准备处理下一个字节
        if (n != 0) {
            tmp |= 0b10000000; // 如果后面还有数据，将最高位（第8位）设置为1，表示后续还有字节
        }
        result.push_back(tmp); // 将当前字节加入结果
    }

    return result; // 返回编码后的字节序列
}

// 将一个数字转换为两位十六进制并输出
// 参数 n: 要转换的数字
// 使用字符串索引方式将数字转为对应的十六进制字符
void print_hex(long long n) {
    // 十六进制字符表，用于查找对应字符
    std::string str = "0123456789ABCDEF";
    // 输出高位(n/16)和低位(n%16)对应的十六进制字符
    std::cout << str[n / 16] << str[n % 16];
}

int main() {

    long long n;
    std::cin >> n; // 从标准输入读取一个整数
    std::vector<long long> result = encode_variant(n); // 对输入的整数进行变长编码

    // 以16进制格式输出编码结果，每个字节宽度为2，前导补0，大写字母
    for (long long i : result) {
        print_hex(i);
        std::cout << " ";
    }

    return 0; // 程序结束
}

{% include custom/custom-post-content-footer.md %}

所有代码已上传至Github：https://github.com/lihongzheshuai/yummy-code
“luogu-”系列题目可在 洛谷题库 在线评测。
“bcqm-”系列题目可在 编程启蒙题库 在线评测。

GESP/CSP 认证学习微信公众号

Last updated on 2025年8月30日

luogu-B3851 [GESP202306 四级] 图像压缩 luogu-B3927 [GESP202312 四级] 小杨的字典