把非负整数按 7 bit 分组编码,低位组带续位标志 1、最高位组带 0,输出十六进制字节。
一种正整数的变长编码方式,规则如下:
(926)₁₀ = (1110011110)₂例:0 编码为 00000000(1 字节);926 编码为 10011110 和 00000111(2 字节)。
输出用两位大写十六进制表示每个字节,空格分隔。
1,是最后一块就写 0。这样做的好处是:小数字只需 1 个字节,大数字可以扩展到多个字节。位运算7 bit 分组续位标志十六进制输出
| 项目 | 说明 |
|---|---|
| 输入 | 第一行 N;随后 N 行每行一个非负整数 |
| 输出 | 每行一个变长编码,两位大写十六进制、空格分隔 |
| 数据范围 | N ≤ 100 |
| 数值范围 | 非负整数(示例含 9 × 10¹⁷ 量级) |
| 分组 | 低位在前,每组 7 bit |
x & 0x7F 取低 7 位,x >>= 7 右移 7 位继续x 变成 0 时,当前的组就是最高位组| 0x80,最后一组不加926 的二进制是 1110011110(共 10 位)。
926 & 0x7F = 926 mod 128
926 = 7 × 128 + 30,所以低 7 位是 30
30 的二进制是 0011110
这不是最后一组(因为右移后还不为 0)→ 补 1 → 10011110 = 0x9E
第 1 个字节:9E(低位组)
926 >> 7 = 7
7 的二进制是 0000111(补足 7 位)
右移后 x = 7 >> 7 = 0 → 这是最后一组 → 补 0 → 00000111 = 0x07
第 2 个字节:07(最高位组)
低位组在前 → 输出顺序为 9E 然后 07
✅ 结果 "9E 07"
| 步骤 | x 的值 | x & 0x7F | 是否最后一组 | 加标志后 | 十六进制 |
|---|---|---|---|---|---|
| 第 1 组 | 926 | 30(0011110) | 否(右移后为 7 ≠ 0) | 10011110 | 9E |
| 第 2 组 | 7 | 7(0000111) | 是(右移后为 0) | 00000111 | 07 |
输出:9E 07 ✓
| 输入 | 二进制 | 分组情况 | 编码结果 |
|---|---|---|---|
| 0 | 0 | 只有一组(全 0) | 00 |
| 1 | 1 | 一组 0000001 | 01 |
| 127 | 1111111 | 一组 1111111,是最后一组 → 01111111 | 7F |
| 128 | 10000000 | 低 7 位 = 0,高位 = 1 → 两组 | 80 01 |
| 926 | 1110011110 | 两组 | 9E 07 |
0:切不出任何组(x 一开始就是 0)
按规则要输出一个全 0 字节 → 00
127:正好 7 位全是 1
它是唯一一组(也是最后一组)→ 最高位补 0 → 01111111 = 0x7F
✅ 特判 0 很关键
128 = 10000000(8 位)
低 7 位 = 0000000 = 0,不是最后一组 → 10000000 = 0x80
右移 7 位后 x = 1 → 是最后一组 → 0000001 = 0x01
✅ 输出 "80 01"
while (x > 0) 循环,x = 0 时一次都不执行,会输出空行。正确做法是先塞入一个 0 组,或者单独判断"若 x == 0 则输出 00"。用 &0x7F 和 >>7 循环取出各组
while (true) { int g = x & 0x7F; x >>= 7; if (x) push(g | 0x80); else { push(g); break; } }——先取低位、再看是否还有,顺序天然正确。把数转成 01 串,按 7 位切分后加标志
| 方案 | 代码量 | 大数友好度 |
|---|---|---|
| 位运算 | 约 10 行 | 高 |
| 字符串 | 约 25 行 | 中 |
每行输入一个非负整数,程序会展示 7 bit 分组过程与编码结果。
点按钮开始 →
#include <bits/stdc++.h> using namespace std; int main() { int n; scanf("%d", &n); while (n--) { unsigned long long x; scanf("%llu", &x); vector<int> bytes; // 存放各字节(低位组在前) if (x == 0) { bytes.push_back(0); // 0 特判:输出一个全 0 字节 } else { while (true) { int g = x & 0x7F; // 取低 7 位 x >>= 7; // 右移 7 位 if (x != 0) { bytes.push_back(g | 0x80); // 不是最后一组,最高位补 1 } else { bytes.push_back(g); // 是最后一组,最高位补 0 break; } } } // 输出:两位大写十六进制,空格分隔 for (int i = 0; i < (int)bytes.size(); i++) { if (i) printf(" "); printf("%02X", bytes[i]); } printf("\n"); } return 0; }
while (true) 而不是 while (x > 0)?因为我们需要在取完最后一组之后再判断一次(用来决定最高位补 0 还是补 1)。如果写成 while (x > 0),就无法区分"当前组是不是最后一组"。while (true) + 内部 break 的写法让判断位置更自然。| 代码 | 作用 | 为什么这样写 |
|---|---|---|
x & 0x7F | 取低 7 位 | 0x7F = 0b1111111 |
x >>= 7 | 右移 7 位 | 把已处理的 7 位丢掉 |
g | 0x80 | 补续位 1 | 0x80 = 0b10000000,置最高位 |
printf("%02X", ...) | 输出十六进制 | %02X 表示至少两位、不足补 0、大写 |
x == 0(会输出空行);② 输出顺序搞反(应该是低位组先输出);③ 用 %02x 小写输出(题目要求大写,用 %02X)。写完程序后,用这些数据自查一遍:
| 输入 | 答案 | 考察点 |
|---|---|---|
0 | 00 | 零值特判 |
1 | 01 | 最小正整数 |
127 | 7F | 恰好 7 位全 1,最高位补 0 |
128 | 80 01 | 刚好多出一位,需要两组 |
926 | 9E 07 | 题面样例 |
255 | FF 01 | 八位全 1 |
while (x > 0) 会让 0 输出空行,应输出 00。%02X(大写的 X)。需要保存各字节(最多 10 个)。
✅ 运算量极小,瞬间完成。这题考的是"位运算 + 续位标志"的编码思路,不是效率。
// 位运算常用掩码 // 0x7F = 0b01111111 取低 7 位 // 0x80 = 0b10000000 置最高位为 1 // 0xFF = 0b11111111 一个字节 // 十六进制输出格式 printf("%02X", v); // 至少 2 位、大写、不足补 0 printf("%02x", v); // 小写版本 printf("%X", v); // 不补 0 // 类似的"变长/前缀"编码思想 // - UTF-8:用字节高位的连续 1 的个数表示"这个字符占几个字节" // - 7-bit 变长整数(protobuf varint):每字节低 7 位是数据、最高位是续位标志 // 本题就是 varint 编码!
把这道题用到的基本功拆出来,它们能迁移到很多同类问题上。
| 能力点 | 本题怎么用 | 还能迁移到 |
|---|---|---|
| 掩码取位 | & 0x7F、>>= 7 | 位运算、编码解码、状态压缩 |
| 续位标志 | 最高位表示"还有下一块" | varint、UTF-8 等变长编码 |
| 十六进制格式化 | %02X | 所有需要固定宽度十六进制输出的题 |