有一道面试题: 给定n个整型数，怎样让这n个数的使用空间最小。
ok，我们都知道在32位的机器下，int类型的数占4个字节，因此n个数总的使用空间应该是4n。（64位不做解释）那我们怎么样才能使得n个数字的使用空间最小呢？
一. 我们先来看一个例子
假设现在有3个数，1,2,3。
我们都知道数字最后都是以二进制的方式存储的，我们可以表示出1，2，3的二进制
1: 0000 0000 0000 0000 0000 0000 0000 0001
2: 0000 0000 0000 0000 0000 0000 0000 0010
3: 0000 0000 0000 0000 0000 0000 0000 0011
正常情况下，要表示1,2,3这三个数，我们必须使用32*3 = 96 bit。我们发现其实这样是非常浪费的，因为对于这三个数来说实际上用到了只是最开始的8个bit，而前面的24个bit都是没有用的。
二. 我们要怎么压缩，才能使得空间变小呢？
如果听说过google protobuf的同学就应该马上能知道，压缩的方式了。没错，方法正是protobuf使用的variant的编码方式。
1. 首先介绍一下什么是protobuf？protobuf是google提出的一种非常强大的结构化数据存储方式，可以通过序列化和反序列化来进行数据操作，详情请走google
2. 介绍一下protobuf的variant的编码方式
普通的一个int二进制是32位，4个字节。而protobuf的一个int并不是这么表示，protobuf会把每个字节的8个bit中最高位当做标记位，标记下一个字节是否属于当前这个数。
比如1，普通的二进制表示是0...0 0000 0001，会占用32位。而protobuf 只要表示成0000 0001，最高位0表示下一个字节不属于当前这个数，因此1只要占用1个字节的空间即可。
3. variant是怎么进行压缩的呢？
假设protobuf要存储一个数300（我们只是单纯考虑压缩，不考虑其它存储的方式因为里面涉及到了key-value键值对，感兴趣的同学可以具体去看看google的文档）。
a.300的二进制如下: 0000 0000 0000 0000 0000 0001 0010 1100
b. 通过上面我们知道，protobuf的每个字节有一个bit用来标记，有7个bit用来表示值。因为我们对300的二进制从后往前每7个bit进行分割，0101100，0000010，0000000，0000000，0000。去掉后面三组都是0，现在只剩下两组0101100，0000010。
因此一个300的varint表示成1010110000000010。只需要占用2个字节，比原来少了2个字节，因此可以节省空间。
c.可能有的同学就会问了，既然variant每个字节只能表示7个bit，那就说4个字节最多只有28个bit能表示值，那么当一个数大于等于2^28的时候不是要用5个字节表示？那当n个数都大于2的28次方的时候，不是比4n的空间还大吗？
没错，这确实是protobuf的一个问题，但是后面我们会有办法来优化这个问题。
4. protobuf的解压缩方式
a. 我们了解了variant的压缩方式之后，应该就能明白是怎么解压缩的了。假设我们拿到了一段variant二进制编码101011000000001010000001....，我们从头开始读，当发现当前自己的最高位为0的是就是说明这个数结束了。
b. 比如我们读到了1010110000000010
第一步，去标记位: 0101100 0000010
第二步，交换数据: 0000010 0101100 这一步看不懂的同学请仔细看一些上面的压缩方式。
第三步，计算: 0000010 0101100 = 2^2 + 2^3 + 2^5 + 2^8 = 300
三. 怎么样做，才能使得空间最小呢？
别忘了，我们还有一个问题没有解决。就是关于当数值大于2^28次方的时候，使用variant编码方式会使得空间大于4*n。
ok，假设有3个数2147483645，2147483646，2147483647。正常情况下存储这三个数需要12个字节，如果使用variant每个数需要5个字节，则要15个字节，发现此时并不能减少空间，反而使空间增大。
在压缩算法里面有一个很经典就是 增量存储。比如这个三个数，我们利用增量存储则可以表示成2147483645，1，1。然后再利用variant存储，则总共只需要5+1+1 = 7个字节，发现此时我们就可以把空间从15压缩到了7，发现收益还是非常可观。
增量存储是一个非常重要的思想，好比搜索引擎的索引。对于一个商业的索引引擎来说，索引可能是有几百亿，对海量的索引进行压缩存储，收益是非常惊人的。
