[GESP202309 四級] 變長編碼

題目描述

小明剛剛學習了三種整數編碼方式：原碼、反碼、補碼，并了解到計算機存儲整數通常使用補碼。但他總是覺得，生活中很少用到 $2^{31}?1$ 這么大的數，生活中常用的 $0～100$ 這種數也同樣需要用 $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$ bit，不足 $7$bit 的在高位用 $0$ 填補。例如， ( 0 ) { 2 } (0)_{\{2\}} (0){2}? 變為$0000000$ 的一組， ( 1110011110 ) { 2 } (1110011110)_{\{2\}} (1110011110){2}? 變為 $0011110$ 和 $0000111$ 的兩組。

3 . 由代表低位的組開始，為其加入最高位。如果這組是最后一組，則在最高位填上 $0$，否則在最高位填上 $1$。于是，$0$ 的變長編碼為 $00000000$ 一個字節， $926$ 的變長編碼為 $10011110$ 和 $00000111$ 兩個字節。

這種編碼方式可以用更少的字節表達比較小的數，也可以用很多的字節表達非常大的數。例如，$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$ 個字節。

你能通過編寫程序，找到一個正整數的變長編碼嗎？

輸入格式

輸入第一行，包含一個正整數 $N$。約定 $0\le N\le 10^{18}$。

輸出格式

輸出一行，輸出 $N$ 對應的變長編碼的每個字節，每個字節均以 $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<uint8_t>存儲編碼結果的字節。
2. 對N進行循環處理,直到N為0:
   • 取N的低7位,記為byte。
   • 將N右移7位。
   • 如果N不為0,說明還有更高位的字節,將byte的最高位設為1。
   • 否則,將more標志設為false,表示已經處理完最后一個字節。
   • 將byte添加到結果vector中。
3. 遍歷結果vector,輸出每個字節的十六進制表示:
   • 如果不是第一個字節,在前面添加一個空格。
   • 以十六進制格式輸出字節,使用大寫字母,寬度為2,不足的在前面補0。
4. 輸出換行符。

C++代碼實現:

#include <iostream>
#include <vector>
#include <iomanip>
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 <iostream>
#include <vector>
#include <iomanip>
#include <sstream>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 <bits/stdc++.h>
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;
}