[GESP202309 四级] 变长编码

题目描述

小明刚刚学习了三种整数编码方式：原码、反码、补码，并了解到计算机存储整数通常使用补码。但他总是觉得，生活中很少用到

2

31

−

1

2^{31}-1

231−1 这么大的数，生活中常用的

0

∼

100

0\sim 100

0∼100 这种数也同样需要用

4

4

4 个字节的补码表示，太浪费了些。
热爱学习的小明通过搜索，发现了一种正整数的变长编码方式。这种编码方式的规则如下：

1 . 对于给定的正整数，首先将其表达为二进制形式。例如，

(

0

)

{

10

}

=

(

0

)

{

2

}

(0)_{\{10\}}=(0)_{\{2\}}

(0){10}​=(0){2}​，

(

926

)

{

10

}

=

(

1110011110

)

{

2

}

(926)_{\{10\}}=(1110011110)_{\{2\}}

(926){10}​=(1110011110){2}​。

2 . 将二进制数从低位到高位切分成每组

7

7

7 bit，不足

7

7

7bit 的在高位用

0

0

0 填补。例如，

(

0

)

{

2

}

(0)_{\{2\}}

(0){2}​ 变为

0000000

0000000

0000000 的一组，

(

1110011110

)

{

2

}

(1110011110)_{\{2\}}

(1110011110){2}​ 变为

0011110

0011110

0011110 和

0000111

0000111

0000111 的两组。

3 . 由代表低位的组开始，为其加入最高位。如果这组是最后一组，则在最高位填上

0

0

0，否则在最高位填上

1

1

1。于是，

0

0

0 的变长编码为

00000000

00000000

00000000 一个字节，

926

926

926 的变长编码为

10011110

10011110

10011110 和

00000111

00000111

00000111 两个字节。

这种编码方式可以用更少的字节表达比较小的数，也可以用很多的字节表达非常大的数。例如，

987654321012345678

987654321012345678

987654321012345678 的二进制为

(

0001101

1011010

0110110

1001011

1110100

0100110

1001000

0010110

1001110

)

{

2

}

(0001101 \ 1011010 \ 0110110 \ 1001011 \ 1110100 \ 0100110 \ 1001000 \ 0010110 \ 1001110)_{\{2\}}

(0001101 1011010 0110110 1001011 1110100 0100110 1001000 0010110 1001110){2}​，于是它的变长编码为（十六进制表示） CE 96 C8 A6 F4 CB B6 DA 0D，共

9

9

9 个字节。

你能通过编写程序，找到一个正整数的变长编码吗？

输入格式

输入第一行，包含一个正整数

N

N

N。约定

0

≤

N

≤

1

0

18

0\le N \le 10^{18}

0≤N≤1018。

输出格式

输出一行，输出

N

N

N 对应的变长编码的每个字节，每个字节均以

2

2

2 位十六进制表示（其中， A-F 使用大写字母表示），两个字节间以空格分隔。

样例 #1

样例输入 #1

0

样例输出 #1

00

样例 #2

样例输入 #2

926

样例输出 #2

9E 07

样例 #3

样例输入 #3

987654321012345678

样例输出 #3

CE 96 C8 A6 F4 CB B6 DA 0D

题目解析

题目描述:
给定一个非负整数N,将其按照变长编码的规则进行编码。变长编码的规则如下:

1. 对于给定的正整数,首先将其表达为二进制形式。
2. 将二进制数从低位到高位切分成每组7bit,不足7bit的在高位用0填补。
3. 由代表低位的组开始,为其加入最高位。如果这组是最后一组,则在最高位填上0,否则在最高位填上1。
4. 将每一组转换为一个字节,字节的高4位和低4位分别对应十六进制数的一位。
5. 将所有字节按照从低位组到高位组的顺序输出,字节之间用空格分隔。

解题思路:

1. 使用vector存储编码结果的字节。
2. 对N进行循环处理,直到N为0:
   • 取N的低7位,记为byte。
   • 将N右移7位。
   • 如果N不为0,说明还有更高位的字节,将byte的最高位设为1。
   • 否则,将more标志设为false,表示已经处理完最后一个字节。
   • 将byte添加到结果vector中。
3. 遍历结果vector,输出每个字节的十六进制表示:
   • 如果不是第一个字节,在前面添加一个空格。
   • 以十六进制格式输出字节,使用大写字母,宽度为2,不足的在前面补0。
4. 输出换行符。

C++代码实现:

#include 
#include 
#include 
using namespace std;

void encodeVarint(uint64_t N) {
    vector<uint8_t> result;
    bool more = true;
    while (more) {
        uint8_t byte = N & 0x7F; // 取低7位
        N >>= 7;
        if (N != 0) {
            byte |= 0x80; // 不是最后一个字节,最高位填1
        } else {
            more = false; // 最后一个字节,最高位填0
        }
        result.push_back(byte);
    }
    for (size_t i = 0; i < result.size(); ++i) {
        if (i > 0) {
            cout << " ";
        }
        cout << hex << uppercase << setw(2) << setfill('0') << (int)result[i];
    }
    cout << endl;
}

int main() {
    uint64_t N;
    cin >> N;
    encodeVarint(N);
    return 0;
}

代码解释:

1. encodeVarint函数接受一个无符号64位整数N,表示要编码的非负整数。
2. 定义result为uint8_t类型的vector,用于存储编码结果的字节。
3. 定义more为布尔类型,初始值为true,表示是否还有更多字节需要处理。
4. 进入循环,直到more为false:
   • 取N的低7位,记为byte。
   • 将N右移7位。
   • 如果N不为0,说明还有更高位的字节,将byte的最高位设为1。
   • 否则,将more标志设为false,表示已经处理完最后一个字节。
   • 将byte添加到resultvector中。
5. 遍历resultvector,输出每个字节的十六进制表示:
   • 如果不是第一个字节,在前面添加一个空格。
   • 使用hex、uppercase、setw(2)和setfill('0')控制输出格式,以十六进制格式输出字节,使用大写字母,宽度为2,不足的在前面补0。
6. 输出换行符。
7. 在main函数中,读入无符号64位整数N,调用encodeVarint函数对N进行变长编码。

这个解答按照你提供的代码实现了变长编码,使用了C++标准库中的vector、iomanip等功能,并通过位运算和移位操作对整数进行处理。

解析2

#include 
#include 
#include 
#include 

using namespace std;

string encodeVarint(uint64_t N) {
    vector<uint8_t> result;
    bool more = true;

    while (more) {
        uint8_t byte = N & 0x7F; // 取低7位
        N >>= 7;
        if (N != 0) {
            byte |= 0x80; // 不是最后一个字节，最高位填1
        } else {
            more = false; // 最后一个字节，最高位填0
        }
        result.push_back(byte);
    }

    stringstream ss;
    for (size_t i = 0; i < result.size(); ++i) {
        if (i > 0) {
            ss << " ";
        }
        ss << hex << uppercase << setw(2) << setfill('0') << (int)result[i];
    }

    return ss.str();
}

int main() {
    uint64_t N;
    cin >> N;

    string encodedString = encodeVarint(N);
    cout << encodedString << endl;

    return 0;
}

解析3

#include 
using namespace std;

long long n;
string a = "0123456789ABCDEF"; // 十六进制的数字

void print(int i) { // 输出
    cout << a[i / 16] << a[i % 16] << " ";
}

int main() {
    cin >> n;
    if (n == 0) {
        cout << "00";
        return 0;
    }
    vector<int> result;
    while (n > 0) {
        int k = n % 128; // 2^7=128，7位一截
        n /= 128;
        if (n > 0) {
            result.push_back(k + 128); // 判断是否为最高位
        } else {
            result.push_back(k);
        }
    }
    reverse(result.begin(), result.end()); // 逆序输出
    for (int byte : result) {
        print(byte);
    }
    return 0;
}