DeFi EVM

Uniswap V3 第7章 Tick 位图：高效查找下一个流动性边界

讲解 Uniswap V3 如何用 tick bitmap 位图在 swap 跨 tick 时高效地找到下一个已初始化的 tick。

5 分钟阅读
Uniswap V3 第7章 Tick 位图：高效查找下一个流动性边界

Uniswap V3 第 7 章：Tick 位图（Tick Bitmap）

swap 跨 tick 时（第 4 章），需要不断回答：“从当前 tick 出发，下一个有流动性边界的 tick 在哪？” 如果一个个遍历所有 tick，gas 会爆炸。V3 用一个精巧的**位图（bitmap）**让这个查找几乎 O(1)。这一章讲清它的原理。

目录

1. 问题：怎么快速找到下一个 tick

V3 的 tick 范围极大（约 ±887272），但绝大多数 tick 是空的（没有任何头寸以它为边界）。只有少数 tick 被”初始化”（有 LP 在此开始或结束区间）。

swap 时价格移动，需要找”下一个已初始化的 tick”来确定这一段 swap 走多远（第 4 章）。如果从当前 tick 逐个 +1 检查，可能要检查上万个空 tick——gas 无法接受。

位图让我们一次检查 256 个 tick。

2. 位图的基本思想

一个 uint256 有 256 个二进制位。我们用每一位代表一个 tick 是否已初始化：

某位 = 1  →  对应 tick 已初始化（有流动性边界）
某位 = 0  →  对应 tick 是空的

这样，一个 uint256 就能记录 256 个 tick 的状态。要找”附近的下一个已初始化 tick”，只需在这个数里找最近的一个 1——用位运算瞬间完成。

3. 二级结构：word 与 bit

tick 太多，一个 uint256 装不下全部。V3 用两级索引：

压缩后的 tick: compressed = tick / tickSpacing   （只考虑合法 tick）
wordPos  = compressed >> 8    （compressed / 256，决定在哪个 uint256）
bitPos   = compressed % 256   （在那个 uint256 里的第几位）

mapping(int16 => uint256) tickBitmap;   // wordPos → 256 位状态
  • 先除以 tickSpacing，因为只有 tickSpacing 的倍数才可能是合法边界（第 6 章），压缩后省空间。
  • 再用高位 wordPos 定位到某个 uint256，用低 8 位 bitPos 定位到其中某一位。

形象地说：tickBitmap 是一排”抽屉”（每个抽屉是一个 uint256/256 个格子），wordPos 选抽屉，bitPos 选格子。

4. 案例：tick 定位到哪个 word 和 bit

设 tickSpacing = 60，某个头寸下界 tick = 1200。

compressed = 1200 / 60 = 20
wordPos = 20 >> 8 = 0          （20 < 256，落在第 0 号 word）
bitPos  = 20 % 256 = 20         （第 0 号 word 的第 20 位）

初始化这个 tick 时，把 tickBitmap[0] 的第 20 位置 1：

tickBitmap[0] |= (1 << 20);

再来一个 tick = 16380：

compressed = 16380 / 60 = 273
wordPos = 273 >> 8 = 1          （落在第 1 号 word）
bitPos  = 273 % 256 = 17         （第 1 号 word 的第 17 位）

5. nextInitializedTickWithinOneWord

核心查找函数：在当前 word 内，找下一个已初始化的 tick。

nextInitializedTickWithinOneWord(tick, tickSpacing, lte):
    compressed = tick / tickSpacing
    if lte (向左/价格下跌方向):
        wordPos, bitPos = position(compressed)
        # 构造掩码：bitPos 及更低位全 1
        mask = (1 << bitPos) - 1 + (1 << bitPos)
        masked = tickBitmap[wordPos] & mask
        # masked 里最高位的 1 就是"下一个更小的已初始化 tick"
        ...
    else (向右/价格上涨方向):
        # 构造掩码：高于 bitPos 的位全 1
        # masked 里最低位的 1 就是"下一个更大的已初始化 tick"
        ...
    如果当前 word 里没有 1，就返回 word 边界（下次循环进入相邻 word）

关键限制：“within one word”——它一次只在当前 256 位的 word 里找。如果这个 word 里没有更多已初始化 tick，就返回 word 的边界，swap 循环会移到相邻 word 继续找。这保证了每次查找的 gas 是有界的（一个 word 的位运算）。

6. 位运算找最近的 1

“在一个 uint256 里找最近的 1”靠位运算：

  • 向右（找更大的 tick）：用 掩码 & bitmap 保留高位，再找最低位的 1（least significant bit）。可用 x & (-x) 取出最低位的 1。
  • 向左（找更小的 tick）：保留低位，找最高位的 1（most significant bit）。用 BitMath.mostSignificantBit。

这些都是常数时间的位操作，不需要循环遍历。

举例：bitmap = 0b...0001_0000_0000（第 8 位是 1），从 bitPos=3 向右找，掩码保留第 3 位以上，masked = 0b...0001_0000_0000，最低位的 1 在第 8 位 → 下一个已初始化的 compressed tick 在第 8 位对应的位置。

7. 本章小结

  1. tick 范围极大但绝大多数为空，swap 跨 tick 需高效找”下一个已初始化 tick”。
  2. 位图：用 uint256 的每一位表示一个（压缩后的）tick 是否已初始化。
  3. 两级索引：compressed = tick/tickSpacing，wordPos = compressed>>8（选 word），bitPos = compressed%256（选位）。
  4. nextInitializedTickWithinOneWord 用掩码 + 找最近的 1，在一个 word 内常数时间查找；word 内无结果则移到相邻 word。
  5. 找最近的 1 用位运算（LSB / MSB），无需遍历——这是 V3 swap 高效跨 tick 的关键。

8. 动手练习

这是一个偏算法的练习，用脚本实现位图查找。

练习：实现 tick bitmap 查找

用 Python 或 Solidity 实现：

  1. 一个 mapping/dict: wordPos → uint256 作为 bitmap。
  2. flipTick(tick, tickSpacing)：把某个 tick 对应的位翻转（初始化/取消）。计算 compressed/wordPos/bitPos 并 bitmap[wordPos] ^= (1 << bitPos)。
  3. nextInitializedTickWithinOneWord(tick, tickSpacing, lte)：实现第 5、6 节的逻辑，返回下一个已初始化 tick（或 word 边界）和是否找到。
  4. 测试：初始化几个 tick（如 60, 1200, 16380），从某个 tick 出发分别向左/向右查找，验证返回正确的相邻已初始化 tick。

进阶（链上）

  • 读一个真实 V3 池的 tickBitmap(wordPos)，解析出哪些 tick 已初始化，和该池的实际头寸分布对照。

运行

forge test --evm-version cancun --fork-url $FORK_URL \
  --match-path test/UniswapV3TickBitmap.t.sol -vvv

下一章（第 8 章 费用算法）讲 V3 最精妙的部分：如何用 feeGrowth 机制，公平地把手续费分配给”价格曾经过其区间”的每个 LP。

💬 评论