AlgoMooc
← 返回题库

P4006. 整数编码

中等通过率 56% · 提交 117 · 通过 66
位运算模拟字符串

小慕正在设计一种高效的整数编码方案,目标是让数值越小的数字,编码后占用的字节数越少。 编码规则如下: 1. 编码时以7位为一组,每个字节的低7位用于存放待编码数字的。 2. 每个字节的最高位用来指示是否还有后续字节:若该位为1,表示后面还有更多字节;若为0,表示当前字节是最后一个字节。 3. 采用编码方式,即低位字节存放在低地址处。 4. 编码结果以十六进制数字符串形式输出,其中小写字母需转换为大写字母。

提示:带虚线的词点一下有通俗解释。

输入描述

输入的为一个字符串表示的非负整数。待编码的数字取值范围为[0, 1 << 64 - 1]

输出描述

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

示例

示例 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输出在后。

时间限制 1000 ms · 内存限制 128 MB

看不懂题目?点开图解(训练营专属)

登录后查看题目图解

题目图解为训练营学员专属内容,请先登录。

微信扫码登录还不是训练营学员?了解训练营 →
写完代码点「提交」,将对全部测试用例判题。