一起谈.NET技术，用c#实现Protocol Buffers的变长字节整形编码

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为底的幂，得出编码后的值

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));
}

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 );
}

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 ));
}