摘要
int在.net里固定占4个字节，如果我们存储和传输大量的int数据，并且大部分数的值比较小，我们就会浪费很多的网络流量和磁盘存储。Protocol Buffers对整数的编码是让值小的数占少量几个的字节，值大的数占多个字节。
编码算法
首先看如下链接，了解Protocol Buffers对整形的编码算法。
它举了个对300的编码，编码后是两个字节：
1010 1100 0000 0010
它这个例子是每个字节左边是高位，可以看到每个字节的最高位是一个标识位，从左到右第一个字节是10101100，最高位是1，说明后面还有字节需要解码，然后第二个字节是00000010，最高位是0，后面没字节了。所以这两个字节就需要解码成一个整数，再往下看。
代码 1010 1100 0000 0010 → 010 1100 000 0010 // 每个字节去掉最高位 → 000 0010 010 1100 // 字节序转换，两个字节互换位置 → 000 0010 ++ 010 1100 // 两个字节进行链接操作（不是相加） → 100101100 // 合并后的结果，高位位0的部分截取掉 → 256 + 32 + 8 + 4 = 300 // 每个值为1的bit位乘以以2为底的幂，得出编码后的值
这个例子是以一个正数为例的，负数也是一样的，不过以补码表示负数的话，有个符号位，而且高位都是1，编码比较复杂，它没有给举例。不过后面咱们用c#实现的变字节编码是支持对负数进行编码的，只是对负数的编码没有压缩的效果。
c#的的二进制基本操作
我们先来熟悉下c#的二进制的位操作，位了查看方便，我们先写一个按二进制打印字节数组的辅助函数：
代码 static string ByteToString( byte [] bytes){ BitArray array = new BitArray(bytes); StringBuilder sb = new StringBuilder(); for ( int i = 0 ; i < array.Length; i ++ ) { sb.Append(array[i] ? ' 1 ' : ' 0 ' ); if ((i + 1 ) % 8 == 0 ) sb.Append( ' ' ); } return sb.ToString();}
来测试查看几个常见的位操作，具体情况详见注释：
代码 private static void StudyBitOperation(){ // 16进制换算成二进制，每个16进制位转换成4个二进制位 // 高位的3是0011，低位的2是0010，因为.net下是小字节序 // 所以0x32的二进制表示是01001100 byte [] temp = new byte [] { 0x32 }; Console.Write( " 0x32的原始二进制表示: " ); Console.WriteLine(ByteToString(temp)); // 左移运算符 (<<) 将第一个操作数向左移动第二个操作数指定的位数。 // 第一个操作数的高序位被放弃，低序空位用 0 填充。移位操作从不导致溢出。 // 01001100左移3位应该是00001001 temp[ 0 ] <<= 3 ; Console.Write( " 左移3位表示: " ); Console.WriteLine(ByteToString(temp)); // 00001001右移2位应该是01001000 temp[ 0 ] >>= 3 ; Console.Write( " 右移2位表示: " ); Console.WriteLine(ByteToString(temp)); // 判断高位第4位是否为1,0x80二进制表示是00000001 // 右移3位是00001000,高位（从右向左以1开始数）第4位是1 // 如果要检查的数高位第4位是1的话，那么两个数按位与后 // 得出的数就只有这位是1，也就是还是00001000 int checkInt = 0x80 >> 3 ; Console.WriteLine( " 高位第4位是:{0} " , (temp[ 0 ] & checkInt) == checkInt); // 把高位第4位设置为0，0x80右移3位是00001000 // 取反后是11110111，和原始字节01001000按位与后 // 就是01000000 checkInt = ~ ( 0x80 >> 3 ); temp[ 0 ] &= ( byte )checkInt; Console.Write( " 把高位第4位设置为0: " ); Console.WriteLine(ByteToString(temp)); // 把高位第3位设置为1,0x80右移2位是00000100 // 和原始字节01000000按位或后就是01000100 checkInt = 0x80 >> 2 ; temp[ 0 ] |= ( byte )checkInt; Console.Write( " 把高位第3位设置为1: " ); Console.WriteLine(ByteToString(temp));}
输出结果：
0x32的原始二进制表示: 01001100 左移3位表示: 00001001 右移2位表示: 01001000 高位第4位是:True把高位第4位设置为0: 01000000 把高位第3位设置为1: 01000100
实现编码及单元测试
响应刀总号召，先写单元测试，我们设计了GetBytesFromInt和GetIntFromBytes分别用来对int数据进行编码和解码，然后单元测试里对各种整数进行编码，然后解码查看是否还是原始数据。
代码 private static void UnitTest(){ UnitTest( 300 ); UnitTest( - 1 ); UnitTest( int .MaxValue); UnitTest( 255 ); UnitTest( 1024 ); UnitTest( 12234234 ); UnitTest( - 12234234 );} private static void UnitTest( int input){ byte [] bytes = GetBytesFromInt(input); if (_debug) Console.WriteLine(ByteToString(bytes)); int result = GetIntFromBytes(bytes); System.Diagnostics.Debug.Assert(input == result); if (_debug) Console.WriteLine(result);}
代码实现，详细算法见注释：
代码 static byte [] GetBytesFromInt( int input){ // 1、得到int的原始字节，.net的整数的二进制表示高位在右边 byte [] bytes = BitConverter.GetBytes(input); BitArray array = new BitArray(bytes); if (_debug) Console.WriteLine(ByteToString(bytes)); // 2、得到多字节编码的字节数，并初始化输出数组 // 原始二进制的每7位要编码到一个字节里，根据这个信息 // 计算出需要多少个字节编码，因为高位在右边，我们就 // 从右往左数，找到第一个为1的二进制位，从这位往 // 左数就都是有效数据位了。 int firstOneIndex = 0 ; for (firstOneIndex = array.Length - 1 ; firstOneIndex >= 0 ; firstOneIndex -- ) { if (array[firstOneIndex]) break ; } int resultBytesLength = ( int )Math.Ceiling(( double )(firstOneIndex + 1 ) / 7 ); byte [] resultBytes = new byte [resultBytesLength]; // 3、设置多字节编码中的每一位, // 每个字节的低7位表示数据位,最高位如果是1表示后面还有数据需要解码 for ( int i = 0 ; i <= firstOneIndex; i ++ ) { // 3.1、计算出本次要编码的目标字节 int byteindex = i / 7 ; byte b = resultBytes[byteindex]; // 3.2、设置本次编码字节的每一位 int checkInt = i % 7 ; b |= array[i] ? ( byte )( 0x01 << checkInt) : ( byte ) 0 ; // 3.3、设置最高位，如果后面还有字节编码则为1，否则为0 if (byteindex < resultBytes.Length - 1 ) b |= 0x80 ; resultBytes[byteindex] = b; } return resultBytes;} static int GetIntFromBytes( byte [] input){ // 1、初始化目标整数的字节数组， // 因为编码数据里有冗余数据,所以要多出一个字节来 byte [] result = new byte [ 5 ]; for ( int i = 0 ; i < input.Length; i ++ ) { // 2、先把多字节编码的每个字节拷贝到目标整数字节中 // 并完成移位，移位是因为多字节编码每字节是7个有效 // 数据位，而.NET的整数的二进制表示是每个字节8个有效 // 数据位，这样目标字节填充几次后，高位就会空出多个 // 位的无效数据 result[i] = input[i]; result[i] >>= i; // 3、从下一个字节的最低位拷贝N位到本次编码的最高位 // 因为本字节右移了i位，所以要从下一个字节拷贝i位数据 // 到本字节 for ( int j = 0 ; j <= i; j ++ ) { // 3.1、得到下一个字节要拷贝的位 int checkInt = 0x80 >> ( 7 - j); if (i + 1 < input.Length) { // 3.2、如果要拷贝的位是1，则设置本字节相应的位为1 if ((input[i + 1 ] & checkInt) == checkInt) { checkInt = 0x80 >> (i - j); result[i] |= ( byte )checkInt; } else // 3.3、如果要拷贝的位是0，则设置本字节相应的位为1 { checkInt = ~ ( 0x80 >> (i - j)); result[i] &= ( byte )checkInt; } } } } if (_debug) Console.WriteLine(ByteToString(result)); return BitConverter.ToInt32(result, 0 );}
单元测试均通过。
存储测试
我们假设要编码的数据都是几万，几千的值，只有很少是大于ushort.max的，随机生成一些整数，用变长字节编码看看是否能起到压缩的效果。
代码 private static void StoreTest(){ Random rnd = new Random(); const int MAX = 1000 ; int sum = 0 ; for ( int i = 0 ; i < MAX; i ++ ) { sum += GetBytesFromInt(rnd.Next( 0 , ushort .MaxValue)).Length; } Console.WriteLine( " .net编码{0}个int需要{1}字节 " , MAX, MAX * 4 ); Console.WriteLine( " Protocol Buffer编码{0}个int需要{1}字节 " , MAX, sum); Console.WriteLine( " 节省了{0:p}的存储空间 " , 1 - ( double )sum / (MAX * 4 ));}
测试输出：
.net编码1000个int需要4000字节Protocol Buffer编码1000个int需要2787字节节省了30. 33 % 的存储空间
当然这个测试数据并不具有代表性，如果要编码的整数大多都是负数，或者很大的正数，那么这种编码不仅不会比原始的int编码小，反而会比.net对整形的定长编码要大。
小节
计算机组成原理讲的知识离我们并不遥远，没准什么时候有个需求来了，你就得用到这些知识。