变长整型

变长整型

大家都知道一般整型int占用32位,我们不管如何储存,他都是4个字节,如果我们有一份数据,里面大部分都是很小的数字(8位即可表示),夹杂了一些32位的大数。这个时候应该如何编码,让他占用空间少一点呢?

变长整型出现了,我们把每个字节看作一个单元,用他的最高位来代表一个拓展信息,信息中储存了什么我们先不要管。那么每个字节的有效储存空间其实是7位。

现在我们已经设计出了一种编码方式,他可以表示所有的7位以内的数据,当然这看起来很傻,第一:有一位被浪费了,第二: 他不能表示超过7位的数据。

让我们现在来利用好这个被浪费的位。如果这一位为1,则代表他将和他后面的一个字节组成一个新的数。如果这一位为0,则代表他就是一个数。

即 0-000 0000 代表000 0000

即 0-000 0001 代表000 0001

即 0-000 0010 代表000 0010

...

即 0-111 1111 代表111 1111

即1-000 0000 代表错误,这个数非法了,因为他后面没有字节了

即1-100 1000 0-100 1000 代表 100 1000 100 1000 -> 10 0100 0100 1000

当然你还能用连续多个1开头的数据来表示更大的位数。

zigzag

很明显,我们解决了正数的编码,负数可不行了,负数的开头是1,一个数的前导0可以省略,但是1是不能省略的。

我们不要使用补码就好了,我们想想原码的定义,最高位为符号位,剩下的位是绝对值

把符号位放到最低位怎么样?完美的解决了。

0 -> 这个数字不存在

00 -> +0

01 -> -0

10 -> +1

11 -> -1

100 -> +10

101 -> -10

110 -> +11

111 -> -11

10101010100101 -> +1010101010010

10101101010101010 -> -1010110101010101

如此编码,负数也可以用很短的字节表示了,配个变长整型,非常完美。