洛谷B3870题（2023年GESP四级）：如何用C++实现数字的变长编码？

一、题目解读

B3870题要求将任意非负整数转换为特定字节编码格式，其核心考察点包括：

1. 大整数二进制转换技术

2. 7位分组编码规则

3. 字节高位标记处理

4. 十六进制输出规范

二、解题思路

解决方案采用以下关键技术：

1. 分层处理架构：先转换二进制，再分组处理，最后字节编码

2. 动态补位机制：通过substr和while循环确保7位分组完整性

3. 双端队列思想：正向分组但反向存储，通过reverse实现顺序校正

4. 位运算优化：采用位或(|)和位移(<<)操作提升编码效率

三、实现步骤

1. 二进制转换阶段：

• 处理n=0特殊情况

• 通过除2取余法获取二进制字符串

• 使用reverse校正位序

2. 7位分组阶段：

• 从低位向高位截取子串

• 动态补0确保每组7位

• 标记是否为末组（pos==0）

3. 字节编码阶段：

• 通过makeByte函数设置最高位标记

• 末组最高位保持0，非末组设为1

4. 输出处理阶段：

• 反转字节顺序满足题目要求

• 用printf格式化输出十六进制

四、完整代码实现（含注释）

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

// 将数字转换为二进制字符串（去除前导0）
string toBinaryString(unsigned long long n) {
    if (n == 0) return "0";
    string binary;
    while (n > 0) {
        binary += (n % 2) + '0';
        n /= 2;
    }
    reverse(binary.begin(), binary.end());
    return binary;
}

// 将7位二进制字符串转换为字节（添加最高位）
char makeByte(const string& bits, bool isLast) {
    char byte = 0;
    for (int i = 0; i < 7; ++i) {
        char bit = (i < bits.size()) ? bits[i] - '0' : 0;
        byte |= bit << (6 - i);
    }
    if (!isLast) byte |= 1 << 7; // 设置最高位为1（如果不是最后一组）
    return byte;
}

// 主处理函数
vector<char> encodeNumber(unsigned long long n) {
    vector<char> bytes;
    if (n == 0) {
        bytes.push_back(0); // 特殊情况：0的编码是00000000
        return bytes;
    }
    
    string binary = toBinaryString(n);
    int len = binary.length();
    int pos = len;
    
    while (pos > 0) {
        int start = max(0, pos - 7);
        string group = binary.substr(start, pos - start);
        pos = start;
        
        // 补足7位
        while (group.length() < 7) {
            group = "0" + group;
        }
        
        bool isLast = (pos == 0);
        bytes.push_back(makeByte(group, isLast));
    }
    
    // 反转字节顺序（因为是从低位开始处理的）
    reverse(bytes.begin(), bytes.end());
    return bytes;
}

int main() {
    unsigned long long N;
    cin >> N;
    
    vector<char> encoded = encodeNumber(N);
    
    // 输出十六进制表示
    for (size_t i =  encoded.size(); i >0; i--) {
        if (i != encoded.size()) cout << " ";
        printf("%02X", (unsigned char)encoded[i-1]);
    }
    cout << endl;
    
    return 0;
}

五、算法总结

该解决方案展现了三个典型工程实践：

1. 防御性编程：对n=0的特殊处理

2. 位操作技巧：makeByte中的位运算组合

3. 数据封装思想：encodeNumber函数的模块化设计 其时间复杂度为O(log n)，空间复杂度O(⌈log n/7⌉)，适合处理大整数场景。