变长编码算法原理与C++实现详解

1. 变长编码算法解析与实现

变长编码（Variable-length encoding）是一种常见的数据压缩技术，它通过为不同频率出现的符号分配不同长度的编码来提高存储效率。在本题中，我们需要实现一种特殊的变长编码方案，将任意正整数转换为字节序列。

1.1 编码原理详解

这种编码方案的核心思想是将整数的二进制表示从低位到高位每7位为一组进行分割，每组形成一个字节（8位）。其中：

• 每个字节的低7位存储实际数据
• 最高位（第8位）作为标志位：0表示这是最后一个字节，1表示后面还有字节

这种编码方式与Protocol Buffers中使用的Varint编码原理相同。它的优势在于：

1. 对小数值特别友好：小于128的数只需要1个字节
2. 对大数值也能有效处理：每增加7位数据只需要增加1个字节
3. 编码解码过程简单高效，只需要基本的位运算

1.2 编码过程示例

以数字300为例，演示编码过程：

1. 二进制表示：300 = 1 0010 1100
2. 分割为7位一组：
   • 第一组（低7位）：010 1100
   • 第二组：000 0010
3. 添加标志位：
   • 第一字节：1010 1100（AC，后面还有字节）
   • 第二字节：0000 0010（02，最后一个字节）
4. 最终编码：AC 02

注意：在实际存储和传输中，通常低位字节在前（小端序），所以先输出AC再输出02。

2. C++实现详解

2.1 代码结构解析

cpp复制#include<bits/stdc++.h>
using namespace std;
typedef long long LL;

int main() {
    LL n;
    cin >> n;
    vector<LL> bytes;
    
    if (n == 0) {
        bytes.push_back(0);
    } else {
        while (n > 0) {
            LL byte = n & 0x7F;
            n >>= 7;
            if (n > 0) {
                byte |= 0x80;