字数 1224，阅读大约需 7 分钟

深入理解 VarInt 与二进制算法

我们经常会在代码中使用到字节类型进行数据的传输，又或者说在计算机中数据本身就是由一个个字节组成，但往往数据的传输会有部分数据是无用的，这次深入探究一下在socket中如何利用VarInt高效传输字节数据。

一、什么是VarInt？

VarInt (Variable-Length Integer) 是一种变长整数编码方式，旨在使用最小的字节数存储整数。一般为1～5个字节，而其特点就是数值越小，所占用的字节也就越小。

在Java中一个int类型固定需要使用4个字节进行传输，无论是多小的数据，均产生4个字节，例如1在Java中表示为 00000000 00000000 00000000 00000001 而非00000001，因此在数据传输时会造成宽带的浪费，为了极致压缩传输数据可以使用varint进行压缩，将数字1的4个字节压缩为1个字节0x01 。

二、VarInt数据结构

VarInt不同于正常的字节，它将每一个字节拆分为两个部分：

• • 最高位（MSB，Bit 7）为标志位，一般称之为Flag ，当最高位为1时，表示后面还有数据，为0时第代表这是最后一个字节。
• • 低7位（Bits 0-6）为数据位，一般称之为Payload，这里存储实际的数值片段。

三、VarInt运算逻辑

这里使用Java进行代码编写，其它语言同理。

编码：int转VarInt

public void writeVarInt(DataOutputStream out, int value) {    while (true) {        // 1. 检查是否只剩最后 7 位        // ~0x7F 是高位掩码，用于检查高位是否还有值        if ((value & ~0x7F) == 0) {            out.writeByte(value); // 剩下的直接写，最高位默认为0 (结束)            return;        }        // 2. 取低7位 + 加上标志位        // (value & 0x7F) -> 取净数据        // | 0x80         -> 强制把最高位变1 (表示未完待续)        out.writeByte((value & 0x7F) | 0x80);        // 3. 处理下一组        value >>>= 7; // 无符号右移7位    }}

上述代码表示将一个传入的int值进行位运算，利用～0x7F将高位取反，利用value进行与运算，检查除了低 7 位之外，高位是否全都是 0（即是否还有剩余数据需要处理）。

• • 0x7F: 0000 ... 0000 0111 1111
• • ~0x7F: 1111 ... 1111 1000 0000

解码：VarInt转Int

public int readVarInt(DataInputStream in) {    int value = 0;    int position = 0; // 位移量：0, 7, 14...    byte currentByte;    while (true) {        currentByte = in.readByte();        // 1. 剥壳并归位        // (currentByte & 0x7F) -> 去掉标志位，只拿数据        // << position          -> 放到对应的权重位置 (0是最低位)        value |= (currentByte & 0x7F) << position;        // 2. 检查结束标志 (最高位是否为0)        if ((currentByte & 0x80) == 0) break;        // 3. 准备下一层        position += 7;        if (position >= 32) throw new RuntimeException("VarInt too big");    }    return value;}

上述代表为编码的反向操作，利用(currentByte & 0x7F)取低位，而后再将数据左移指定位数，如果当前是第一个字节则不需要进行左移，暂存当前数值。

然后再次进行运算取当前字节最高位，判断是否为0，否则继续进行下一层，并将position+7，准备下次位移，读取新字节。

最终将读取到的字节进行合并计算得到结果。

四、字节读取位置

在读取数据时，有一个可能会搞混的地方，即每次只读取一个字节进行处理，因此在解码运算时会进行位移计算，即position+7。VarInt是一个低位在前的小端序编码，因此在读取时是从低位→高位进行读取。

试着这样理解，把VarInt分为4个小块（实际上需要5个小块，因为需要5个字节），在进行解码时，需要将第一次解码读取到的字节放到低位，也就是最右侧的第一个小块，第二次读取到的字节依次往左放，这就有了向左位移的操作了。

Tip

避坑：在Java中Byte 是有符号的：Java 的 byte 范围是 -128 到 127。所以读到 0xAC (172) 时，Java 会认为是 84。而使用位运算则不在乎符号。只要使用 &、|、<< 操作，二进制位的状态是不变的，计算结果依然正确。如果需要做十进制数学运算，则需要使用 b & 0xFF 转为无符号 int。