> ## Content Index
> Fetch the complete content index at: https://huizhou92.com/llms.txt
> Use this file to discover other available public pages before exploring further.

# 解析Go: varint 的使用与实现原理
- URL: https://huizhou92.com/jie-xi-go-varint-de-shi-yong-yu-shi-xian-yuan-li/
- Published: 2024-09-06T07:33:15.000Z
- Updated: 2026-09-06T11:39:05.000Z
- Author: huizhou92
- Tags: tech, go, #lang-zh-cn

最近发现 `Golang` 标准库竟然自带了 `varint` 的实现，代码位置在 [encoding/binary/varint.go](https://github.com/golang/go/blob/9e9b1f57c26a6d13fdaebef67136718b8042cdba/src/encoding/binary/varint.go?ref=huizhou92.com)，这个跟protobuf里面的varint实现基本是一致的。刚好借助 `golang` 标准库的 `varint` 源码，我们来系统地学习和梳理下 `varint`。  
熟悉 `protobuf` 的人肯定对 `varint` 不陌生，`protobuf` 里面除了带 fix (如 fixed32、fixed64) 之外的整数类型, 都是 `varint` 编码。  
`varint` 的出现主要是为了解决两个问题：

1. **空间效率**：以 `uint64` 类型为例，可以表示的最大值为 18446744073709551615。然而在实际业务场景中，我们通常处理的整数值远小于 uint64 的最大值。假设在我们的业务中，需要处理的整数值仅为 1，但在网络传输过程中，我们却需要使用 `8 个字节`来表示这个值。这就导致了大量的空间浪费，因为大部分字节并没有实际存储有效的信息。varint 编码通过使用可变长度的字节序列来表示整数，使得小的整数可以用更少的字节表示，提高空间效率。
2. **兼容性**：varint 使得我们可以在不改变编码 / 解码逻辑的情况下，处理不同大小的整数。这意味着我们可以在不破坏向后兼容性的情况下，将一个字段从较小的整数类型（如 uint32）升级到较大的整数类型（如 uint64）

本文将通过分析 Golang 标准库自带的 varint 源码实现，介绍 varint 的设计原理以及Golang标准库是如何解决 varint 在编码负数时遇到的问题。

> This article was first published in the Medium MPP plan. If you are a Medium user, please follow me on [Medium](https://medium.huizhou92.com/?ref=huizhou92.com). Thank you very much.

## Varint 的设计原理

varint 的设计原理非常简单：

- 7bit 为一组：将整数的二进制表示分为 7 个 bit 位一组。从低位到高位，每 7 个 bit 位作为一个单元。
- 最高位表示 “继续” 标志。在每个 7 位的单元前面添加一个标志位，形成一个 8 位的字节。如果后面还有更多的字节，这个标志位就设置为 1，否则设置为 0。  
例如：对于一个整数 `uint64(300)`，它的二进制表示是 `100101100`。我们可以将它分为两组，即 `10` 和 `0101100`。然后在每组前面添加标志位，得到两个字节 `00000010` 和 `10101100`，这两个字节就是 300 的 `varint` 编码。相比于用 `uint64` 的 4 字节表示，少了 75% 的存储空间。

```go
func main() {  
    v := uint64(300)  
    bytes := make([]byte, 0)  
    bytes = binary.AppendUvarint(bytes, v)  
    fmt.Println(len(bytes))  
    for i := len(bytes); i > 0; i-- {  
       fmt.Printf("%08b ", bytes[i-1])  
    }  
}

```

![Figure 1: varint encoding ](https://images.hxzhouh.com/blog-images/2024/09/5968188c58521a4262e1c0f76fcc010a.png)

## 无符号整数的 Varint

在 `Golang` 标准库中有两套 `varint` 的函数: 分别用于无符号整数的 [PutUvarint](https://github.com/golang/go/blob/9e9b1f57c26a6d13fdaebef67136718b8042cdba/src/encoding/binary/varint.go?ref=huizhou92.com#L51)和 [Uvarint](https://github.com/golang/go/blob/9e9b1f57c26a6d13fdaebef67136718b8042cdba/src/encoding/binary/varint.go?ref=huizhou92.com#L68)，以及用于有符号整数的 [Varint](https://github.com/golang/go/blob/9e9b1f57c26a6d13fdaebef67136718b8042cdba/src/encoding/binary/varint.go?ref=huizhou92.com#L115) 和 [PutVarint](https://github.com/golang/go/blob/9e9b1f57c26a6d13fdaebef67136718b8042cdba/src/encoding/binary/varint.go?ref=huizhou92.com#L101)  
我们先看下无符号整数的 varint 实现，代码如下：  
list1: go src PutUvarint

```go
func PutUvarint(buf []byte, x uint64) int {
	i := 0
	for x >= 0x80 {
		buf[i] = byte(x) | 0x80
		x >>= 7
		i++
	}
	buf[i] = byte(x)
	return i + 1
}

```

代码里有个非常重要的常量：0x80，对应于二进制编码就是 `1000 0000`。这个常量对接下来的逻辑非常重要：

1. `x >= 0x80`。这意味着 x 的二进制表示形式至少有 8 位，我们刚才讲到 7 个 bit 位为一组，那 x 就需要被拆分了。
2. `byte(x) | 0x80`。将 x 的最低 8 位与 `1000 0000` 进行按位或操作，然后将结果存储在 buf\[i\] 中。这样 **既可以将最高位设置为 1，同时也提取出了 x 的最低 7 位**。
3. `x >>= 7`. 将 x 右移 7 位，处理下一个分组。
4. `buf[i] = byte(x)`。当 for 循环结束时，即意味着 x 的二进制表示形式最高位必然是 0。此时就不用做额外的补零操作了。

`Uvarint` 是 `PutUvarint` 的逆过程。

需要注意的是，varint 将整数划分为 7 位一组。这意味着，对于大整数 varint 将会出现负向优化。例如对于 uint64 的最大值来说，本来只需要 8 个 byte 来表示，但在 varint 中却需要 10 个字节来表示了。（`64/7 ≈ 10`）

## 负数的编码：zigzag 编码

看似 varint 编码已经完美无缺了，但以上忽略了一点：负数的存在。

我们知道，在计算机中数字是用补码来表示的，而负数的补码则是将其绝对值按位取反再加 1。这就意味着一个很小的负数，它的二进制形式对应于一个非常大的整数。  
例如：对于一个 32 位的整数 `-5` 来说，其绝对值 5 的二进制形式是 `101`。 但 `-5` 的二进制形式却是 `11111111111111111111111111111011`，如果使用 `varint` 对其编码, 需要 5 个字节才能表示。

Golang标准库引入了 `zigzag` 编码来解决这个问题，`zigzag` 的原理非常简单：

- 对于正数 n，会将其映射为 `2n`。例如整数 2，经过 zigzag 编码之后变成了 4。
- 对于负数 `-n` 来说，会将其映射为 `2n-1`。例如负数 `-3`，经过 zigzag 编码之后变成了 5。

**这样负数和正数在数值上完全不会冲突，正整数和负整数交错排列**，这也是为什么叫做 zigzag 编码 (锯齿形编码）的原因。  
同时，负数被转换成正数之后，二进制编码也精简了许多。  
例如： 对 `int32(-5)` 进行 zigzag 编码后，变成了 9，对应于二进制为 `00000000000000000000000000001001`，使用 1 个字节即可表示 varint。  
我们看下 Golang 标准库的实现，代码如下：

```go
func PutVarint(buf []byte, x int64) int {
	ux := uint64(x) << 1
	if x < 0 {
		ux = ^ux
	}
	return PutUvarint(buf, ux)
}

```

从代码可以看出，对于有符号整数的varint实现，golang标准库这里分成了两步：

1. 先对整数进行 zigzag 编码进行转换
2. 对转换之后的数值再进行 varint 编码  
对于负数，多了一步 `ux = ^ux` ，这就有些难以理解了，为什么这么转换之后就等于`2n - 1`了？

我们可以大概推导下整个过程，假设我们有个整数 `-n`：

1. 对原数值先左移，再进行取反。其实可以看做：对原数值先取反，再左移，然后+1。 即 `2*(~(-n))+1`
2. 我们知道`负数的补码=绝对值按位取反+1`，那如何根据补码再推导出绝对值？这里有个公式是：`|A| = ~A+1`
3. 我们将这个公式带到第一步的式子里面： `2*(n-1) + 1 = 2n - 1`。这就完美对应上了负数的 ZigZag 编码 (数学多么美妙)。

![Figure 2: ZigZag encoding ](https://images.hxzhouh.com/blog-images/2024/09/4a36258701ba672eb68d4ec7da38285e.png)

在 Golang 标准库里面，调用 `PutUvarint` 时只会使用 `varint` 编码，调用 `PutVarint` 会先进行 `zigzag` 编码，再进行 `varint` 编码。  
而在 `protobuf` 中，如果类型是` int32`、`int64`、`uint32`、`uint64`，只会使用 `varint` 编码。使用 `sint32`、`sint64` 将先进行 `zigzag` 编码，再进行 `varint` 编码

## Varint 不适用的情况

虽然 varint 编码设计非常精妙，但并不适用于所有的场景：

- **大整数**：对于非常大的整数，varint 编码可能会比固定长度的编码更消耗空间。例如当所有的整数值域大于 `2^63`，那使用 varint 会用到 10 字节。相比于传统的八字节整数，反而多用了 25% 的空间
- **需要快速随机访问的数据**：由于 varint 是变长编码，所以我们无法直接通过索引来访问特定的整数，必须从头开始解码，直到找到我们需要的整数。这使得 varint 编码不适合用于需要快速随机访问的数据。
- **需要频繁进行数学运算的数据**：由于 varint 编码的数据需要先解码才能进行数学运算，所以如果一个应用需要频繁地对数据进行数学运算，那么使用 varint 编码可能会导致性能下降。
- **安全敏感的应用**：varint 编码的数据可能会暴露出一些关于原始整数的信息，例如它的大小。在某些安全敏感的应用中，这可能是不可接受的。