首页 > 试题广场 >

正整数压缩算法

[编程题]正整数压缩算法
  • 热度指数:96 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 256M,其他语言512M
  • 算法知识视频讲解
我们知道一个32位的正整数需要4个字节来表示,但对于3,23这类小的正整数,其实用一个字节就可以表示了,因此我们可以通过一些算法来对32位的正整数进行编码,从而达到压缩的目的。这里我们采用如下方式来压缩正整数:
1. 每个字节由8个bit组成,我们将最高位的bit作为标志位。
2. 如果标志位为0,那么说明后续还有其它字节。
3. 如果标志位为1,那么表示后续没有更多的字节了。

举两个例子:
1. 25的二进制表示为:0001, 1001,因为只需要一个字节表示,因此将其最高bit设置为1,得到压缩后的二进制表示为:1001, 1001
2. 300的二进制表示为:0000, 0001, 0010, 1100,需要两个字节表示。因此,我们将该二进制的低7个bit拿出来作为最后一个字节,同时由于是最后一个字节,因此,其标志位设置为1,从而得到压缩后的最后一个字节为1010, 1100;去除最低的7个bit后,剩余部分组成前一个字节,同时因为还有后续字节,因此将其标志位设置为0, 从而得到压缩后的字节为:0000, 0010。将两个字节拼接,得到300压缩后的二进制表示:0000, 0010, 1010, 1100


输入描述:
一个整数


输出描述:
该整数压缩后的二进制表示
示例1

输入

25

输出

10011001
示例2

输入

300

输出

0000001010101100

这道题你会答吗?花几分钟告诉大家答案吧!