填空题

正整数压缩算法

Question

我们知道一个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

输入描述： 一个整数输入样例： 25 输出描述： 该整数压缩后的二进制表示输出样例 10011001