nexthexonextbutterflyvolantisyearnyiliashokaindigoapollolandscapecactusmateryicarusfluidmaterial

变长整型

大家都知道一般整型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

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