整数编码 - 华为OD统一考试(A卷、C++)

题目描述

实现一种整数编码方法，使得待编码的数字越小，编码后所占用的字节数越小。

编码规则如下:

1. 编码时7位一组，每个字节的低7位用于存储待编码数字的补码。
2. 字节的最高位表示后续是否还有字节，置1表示后面还有更多的字节，置0表示当前字节为最后一个字节。
3. 采用小端序编码，低位和低字节放在低地址上。
4. 编码结果按16进制数的字符格式输出，小写字母需转换为大写字母。

输入描述

输入的为一个字符串表示的非负整数

输出描述

输出一个字符串，表示整数编码的16进制码流

待编码的数字取值范围为[0，1<<64-1]

示例1

输入：
0

输出：
00

说明：
输出的16进制字符，不足两位的前面补0，如00、01、02。

示例2

输入：
100

输出：
64

说明：
1000的二进制表示为0011 1110 1000，至少需要两个字节进行编码；
第一个字节最高位置1，剩余的7位存储数字1000的第一个低7位（110 1000），所以第一个字节的二进制为1110 1000，即E8；
第二个字节最高位置0，剩余的7位存储数字1000的第二个低7位（000 0111），所以第一个字节的二进制为0000 0111，即07；
采用小端序编码，所以低字节E8输出在前，高字节07输出在后。

示例3

输入：
1000

输出：
E807

说明：
1000的二进制表示为0011 1110 1000，至少需要两个字节进行编码；
第一个字节最高位置1，剩余的7位存储数字1000的第一个低7位（110 1000），所以第一个字节的二进制为1110 1000，即E8；
第二个字节最高位置0，剩余的7位存储数字1000的第二个低7位（000 0111），所以第一个字节的二进制为0000 0111，即07；
采用小端序编码，所以低字节E8输出在前，高字节07输出在后。

C++

#include <bits/stdc++.h>

using namespace std;

// 编码函数：每7位为一组，小端序，16进制大写输出
string encodeInteger(const string& numStr) {
    vector<string> result;
    unsigned long long num = 0;

    // 将字符串形式的大整数转换为数值（适用于较大范围）
    for (char ch : numStr)
        num = num * 10 + (ch - '0');

    do {
        // 取最低7位（0x7F = 127）
        unsigned char byte = num & 0x7F;
        num >>= 7; // 右移7位，准备下一组

        // 如果后面还有未处理的位，则将当前字节的最高位设置为1（0x80 = 128）
        if (num > 0)
            byte |= 0x80;

        // 格式化为两位大写十六进制字符串（不足两位补0）
        stringstream ss;
        ss << uppercase << hex << setw(2) << setfill('0') << (int)byte;
        result.push_back(ss.str());
    } while (num > 0);

    // 将所有字节按顺序拼接成最终输出字符串（小端序）
    string output;
    for (const auto& s : result)
        output += s;

    return output;
}

int main() {
    string input;
    // 读取一行输入（可能是超大整数）
    getline(cin, input);

    // 调用编码函数并输出结果
    cout << encodeInteger(input) << endl;
    return 0;
}

解题思路：

题目要求我们将一个整数编码为一串十六进制字符流，遵循如下规则：

1. 每7位为一组，用于编码原数字的补码（二进制表示）。
2. 每个字节的最高位（第8位）是控制位，若后续还有字节需要编码，则设置为 1，否则为 0。
3. 小端序：编码时低字节（低位的7位）在前，高字节在后。
4. 输出格式为大写的16进制字符串（如E8，07），且每个字节固定输出2位（不足补0）。

举个例子（以数字 1000 为例）：

• 二进制为：1111101000，即 10 位；
• 按照 7 位拆分，得到：
  • 第 1 个 7 位：1101000（低位）
  • 第 2 个 7 位：0000111（高位）
• 第 1 个字节最高位设置为 1 → 11101000 = E8
• 第 2 个字节最高位设置为 0 → 00000111 = 07
• 小端序：输出顺序为 E8 07

整理题解不易， 如果有帮助到您，请给点个赞 ‍❤️‍ 和收藏 ⭐，让更多的人看到。🙏🙏🙏