洛谷B3870题：位操作与二进制转换解决变长编码

一、题目解读

洛谷B3870题要求将给定的无符号长整型数转换为可变长度的字节编码，并输出其十六进制表示。题目核心在于设计一种高效的编码方案，需处理数字的二进制位分组、最高位标记及字节顺序反转等细节。该问题考察对二进制位操作的理解与算法逻辑的严谨性，尤其在边界条件（如0的特殊编码）与分组补位机制上的实现。

二、解题思路

1. 二进制转换与去前导0：自定义toBinaryString函数将数字转为二进制串，通过倒序取余法生成，并去除前导0（避免无效位）。

2. 分组与最高位标记：将二进制串按7位分组，不足位补0。通过makeByte函数生成字节，非最后一组设置最高位为1，区分数据段与结束标志。

3. 字节反转输出：因处理从低位开始，最终需反转字节顺序，确保正确解码顺序。

4. 边界处理：0的特殊情况单独编码为单字节0，避免空输出。

三、解题步骤

1. 输入数字N：通过cin获取用户输入的无符号长整型数。

2. 二进制转换：调用toBinaryString(N)生成二进制串，去除前导0。

3. 分组编码：

○ 从末尾开始，每次取最长7位子串（不足补0）。

○ 通过makeByte将子串转为字节，根据位置标记最高位。

○ 存入bytes容器，记录编码结果。

4. 字节反转：使用reverse函数反转字节顺序，确保高位在前。

5. 输出十六进制：循环遍历字节，按格式%02X输出，空格分隔。

四、代码与注释

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

// 将数字转换为二进制字符串（去除前导0）
string toBinaryString(unsigned long long n) {
    if (n == 0) return "0"; // 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; // 不足位补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编码为单字节0
        return bytes;
    }
    
    string binary = toBinaryString(n);
    int len = binary.length();
    int pos = len;
    
    while (pos > 0) {
        int start = max(0, pos - 7); // 从末尾开始取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;
}

五、总结

该解法通过模块化函数（二进制转换、字节生成、主逻辑）实现清晰编码流程，兼顾效率与边界处理。核心技巧在于：

● 二进制倒序生成避免额外反转操作；

● 分组补位与最高位标记简化解码逻辑；

● 字节反转确保大端序输出。

适用于需处理变长二进制数据的场景，算法简洁且易于扩展。未来可探索更紧凑的位运算优化，或结合动态规划优化分组效率。