题目描述

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

编码规则如下：

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

输入的为一个字符串表示的非负整数，输出一个字符串，表示整数编码的 16 进制码流。

解题思路

1. 编码逻辑：
   • 使用一个循环，每次从输入数字中提取出 7 位，直到数字变为 0。
   • 通过位运算提取出低 7 位，判断是否还有更多字节需要编码。
   • 将提取出的字节的高位设置为 1 或 0，并保存结果。
2. 转换为十六进制：
   • 将每个字节转换为 16 进制表示，并保证每个字节输出时至少两位。
3. 小端序：由于是小端序，编码结果需要反转。

复杂度分析

• 时间复杂度：O(n)，其中 n 是待编码数字的位数（最多需要 n/7 个字节来表示数字）。
• 空间复杂度：O(1)，只使用了常数空间来存储变量。

下面是带有注释的代码实现，分别为 C++、Java 和 Python 版本。

C++

#include <bits/stdc++.h>
using namespace std;

int main() {
    long num;
    cin >> num;  // 读取输入的非负整数

    // 用于存储最终的编码结果
    vector<string> hexCodes;  

    do {
        // 取出当前数字的低7位
        long long lowBit = num & ((1<<7)-1); 

        // 检查是否还有更多位需要编码
        if (num >> 7 > 0) { 
            lowBit |= (1<<7);  // 设置最高位为1
        }

        // 将当前字节转换为16进制字符串
        stringstream ss;
        ss << hex << lowBit;
        string hexStr(ss.str());

        // 确保16进制字符串至少为两位
        if (hexStr.length() == 1) {
            hexStr = "0" + hexStr;  // 前面补零
        }

        // 转换为大写并保存结果
        for (char c : hexStr) {
            cout << (char)toupper(c);
        }

        // 右移运算，移除num的低七位
        num >>= 7;

    } while (num != 0);  // 循环直到num为0

    cout << endl;  // 输出结束后换行

    return 0;
}

Java

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        long num = scanner.nextLong();  // 读取输入的非负整数

        while (true) {
            long lowBit = num & ((1 << 7) - 1);  // 取出低7位

            if (num >> 7 > 0) { 
                lowBit |= (1 << 7);  // 设置最高位为1
            }

            String hexStr = Long.toHexString(lowBit);  // 转换为16进制并转换为小写
            hexStr = hexStr.toUpperCase();  // 转换为大写

            if (hexStr.length() == 1) {
                System.out.print("0");  // 输出前导零
            }

            System.out.print(hexStr);  // 输出16进制字符串

            if (num >> 7 == 0) {  // 如果没有更多位，退出循环
                break;
            }
            
            num >>= 7;  // 右移运算，移除num的低七位
        }

        System.out.println();  // 换行
    }
}

Python

def main():
    num = int(input())  # 读取输入的非负整数

    while True:
        low_bit = num & ((1 << 7) - 1)  # 取出低7位

        if num >> 7 > 0: 
            low_bit |= (1 << 7)  # 设置最高位为1

        hex_str = hex(low_bit)[2:]  # 转换为16进制并去掉'0x'

        if len(hex_str) == 1:
            print("0", end='')  # 输出前导零

        for c in hex_str.upper():  # 转换为大写并输出
            print(c, end='')

        if num >> 7 == 0:  # 如果没有更多位，退出循环
            break
        
        num >>= 7  # 右移运算，移除num的低七位

    print()  # 换行

if __name__ == "__main__":
    main()

题目描述

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

编码规则如下:

编码时 $7$ 位一组，每个字节的低 $7$ 位用于存储待编码数字的补码

字节的最高位表示后续是否还有字节，置 $1$ 表示后面还有更多的字节，置 $0$ 表示当前字节为最后一个字节。

采用小端序编码，低位和低字节放在低地址上。

编码结果按 $16$ 进制数的字符格式输出，小写字母需转换为大写字母

输入描述

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

输出描述

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

备注

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

样例1

输入

0

输出

00

说明

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

样例2

输入

100

输出

64

说明

$100$ 的二进制表示为 $0110$ $0100$，只需要一个字节进行编码;

字节的最高位置 $0$ ，剩余 $7$ 位存储数字 $100$ 的低 $7$ 位 ($110$ $0100$) ，所以编码后的输出为 $64$ 。

样例3

输入

1000

输出

E807

说明

$1000$ 的二进制表示为 $0011$ $1110$ $1000$ ，至少需要两个字节进行编码;

第一个字节最高位置 $1$ ，剩余的 $7$ 位存储数字 $1000$ 的第一个低 $7$ 位 ($1101000$)，所以第一个字节的二进制为 $1110$ $1000$ ，即 $E8$ ;

第二个字节最高位置 $0$ ，剩余的 $7$ 位存储数字 $1000$ 的第二个低 $7$ 位 ($0000111$)，所以第一个字节的二进制为 $0000$ $0111$，即 $07$ ;

采用小端序编码，所以低字节 $E8$ 输出在前，高字节 $07$ 输出在后。