在数据传输中（或者数据存储中），有一个问题经常存在。比如以标准的int类型来说，是32位，8个字节，在实际使用过程中，整形的数值未必非常大，但是却要占用4个字节来存储，在空间上是极大的浪费，在数据传输中，也增加了数据传输量，不够绿色与高效。

在看了简单的老王的小而巧的数字压缩算法：zigzag一文后，并参考了部分实现，比如Google的protocol buffers¹的实现后，深入了解了这个有意义的数字压缩算法。

算法的基本思想是，将数字按照7位进行分组，这样，最坏的情况下，32位的整数需要5个字节（40位）来传输，但这种情况还是较少，普遍的情况是只需要2-3个字节就可以存储大部分的数字。

分组后的数字，从低位开始转化，如果有后续的字节，则该字节的首位（msb，most significant bit）置为1，如果是最后一个字节，则msb为0。举个整数例子12345，实际只使用了2个字节，如果按传统方式存储，就需要4个字节存储，浪费2个字节：

0011 0000 0011 1001

分组：

1100000 0111001

正好分成两组，建立一个字节数组buf[n]，从低位开始，0111001前加上msb 1 变成 10111001。

buf[0] = 10111001
buf[1] = 01100000

转换完毕，只需要2个字节就完成了一个4字节整形的编码。

解码的过程是其逆过程，先看msb是否为1，为1的话，将其放入整形的低位，继续下一个字节，如果是0，将其放入整形中后停止。

下面是Google protocol buffers 的Go语言实现，很轻巧。

编码

// https://github.com/golang/protobuf/blob/master/proto/encode.go
func EncodeVarint(x uint64) []byte {
	var buf [maxVarintBytes]byte
	var n int
	for n = 0; x > 127; n++ {
		buf[n] = 0x80 | uint8(x&0x7F)
		x >>= 7
	}
	buf[n] = uint8(x)
	n++
	return buf[0:n]
}

解码

//https://github.com/golang/protobuf/blob/master/proto/decode.go
func DecodeVarint(buf []byte) (x uint64, n int) {
	// x, n already 0
	for shift := uint(0); shift < 64; shift += 7 {
		if n >= len(buf) {
			return 0, 0
		}
		b := uint64(buf[n])
		n++
		x |= (b & 0x7F) << shift
		if (b & 0x80) == 0 {
			return x, n
		}
	}

	// The number is too large to represent in a 64-bit value.
	return 0, 0
}

走到这一步，大部分的问题基本解决了，但还有一个问题，上面的程序主要面对无符号整数或者正整数，如果是负数呢？

那么负数一般是如何表示的呢？负数的最高位设为1，因此我们可以将整数整体左移1位，然后将符号位放到最低位。比如，-12345的二进制存储是，先绝对值求反得反码，然后加1得到补码：

0011 0000 0011 1001

求反

1111 1111 1111 1111 1100 1111 1100 0110

加1得到补码：

1111 1111 1111 1111 1100 1111 1100 0111

下面进行编码，先左移1 位：

1111 1111 1111 1111 1001 1111 1000 1110

然后与补码右移31位

1111 1111 1111 1111 1111 1111 1111 1111

上述两者进行异或 ^运算，可以得到

0110 0000 0111 0001

又是一个小数值，再继续按照前述的方法编码即可。

EncodeVarint(uint64((x << 1) ^ uint64((int64(x) >> 63))))

解码的方式相反，根据之前的解码方式获得0110 0000 0111 0001后，先右移一位，然后进行异或运算。

x = (x >> 1) ^ uint64((int64(x&1)<<63)>>63)

其中x >> 1：

0011 0000 0011 1000

uint64((int64(x&1)<<63)>>63)值为

1111111111111111111111111111111111111111111111111111111111111111