#4217. 变长编码(23-9C++四级)

变长编码(23-9C++四级)

变长编码

【问题描述】

小明刚刚学习了三种整数编码方式:原码、反码、补码,并了解到计算机存储整

数通常使用补码。但他总是觉得,生活中很少用到 -1这么大的数,生活中常

用的0~100这种数也同样需要用4个字节的补码表示,太浪费了些。热爱学习的

小明通过搜索,发现了一种正整数的变长编码方式。这种编码方式的规则如下:

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

2. 将二进制数从低位到高位切分成每组7bit,不足7bit的在高位用0填补。例
如, 变为00000000一组,
3. 由代表低位的组开始,为其加入最高位。如果这组是最后一组,则在最高位

填上0,否则在最高位填上1。于是,0的变长编码为00000000一个字节,926的变长编码为10011110和00000111两个字节。

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

,于是它的变长编码为(十六进制表示)CE 96 C8 A6 F4 CB B6 DA 0D,共 9个字节。你能通过编写程序,找到一个正整数的变长编码吗?

【输入描述】

输入第一行,包含一个正整数N。约定 。

【输出描述】

输出一行,输出N对应的变长编码的每个字节,每个字节均以2位十六进制表示(其中,A-F使用大写字母表⽰),两个字节间以空格分隔。

【样例输入1】

0

【样例输出1】

00

【样例输入2】

926

【样例输出2】

9E 07

【样例输入3】

987654321012345678

【样例输出3】

CE 96 C8 A6 F4 CB B6 DA 0D

【题目大意】

输入一个正整数N,转换为二进制数,将二进制数从低位到高位切分成每组7bit,

不足7bit的在高位用0填补。由代表低位的组开始,为其加入最高位。如果这组

是最后一组,则在最高位填上0,否则在最高位填上1。最后转换为十六进制数

输出。

【解题思路】

本题主要考察内置函数,for…else..语句和字符串方法的使用。

  1. 输入正整数N,使用bin()函数,转为二进制数并去掉二进制数的前缀,再赋

值给N。

  1. 判断二进制N是否是7位,不是择在前面补0。

3.设置一个空列表bList,用来存放二进制数,使用for循环遍历N,每7位位

一个列表项。

4.逆序存储在bList中,除了最后一个列表项,“1”+每个列表项。最后一项,“0”+

每个列表项。

5.设置一个空字符串rst,遍历bList,使用int()函数将每个遍历元素(即列表项)

转为10进制数,再使用hex()函数转为16进制数并使用字符串切片去除进制前

缀“0x”。使用upper()函数将字母转为大写字母,使用zfill()函数在字符串的左侧

填充零,直到达到指定的长度2。最后用空字符串分割。

6.去掉最后的空字符输出rst。

Limitation

1s, 1024KiB for each test case.