# 3. $R[d]$ Left Shift

在 Bitap 算法中，左移一位表示消耗一个模式字符，这是因为状态位向量中每一位的位置与模式中已匹配的字符数直接对应，而左移操作正是将模式相对于文本向右滑动一个字符。

下面从位向量的定义、对齐关系和位运算语义三方面解释。

1. 位向量的位与模式字符的对应关系

设模式长度为 $m$ 。状态位向量 $R[d]$ 有 $m$ 位。
通常约定：

例如模式 $P = \text{"AC"}$ ， $m=2$ ：

位	对应模式字符
位 0 (LSB)	`'A'`（第 1 个）
位 1 (MSB)	`'C'`（第 2 个）

位值为 0 表示匹配，1 表示不匹配。

Bitap 从文本末尾向前遍历（for i in (n-1):-1:0）。
当处理完文本位置 $i$ 后，下一步处理位置 $i-1$ 。
这意味着文本向左移动了一个位置，而模式相对于文本就相当于向右滑动了一个字符。

假设当前状态 $R[d]$ 表示：从文本位置 $i$ 开始，模式的前若干个字符已经与文本匹配。
现在我们要处理文本位置 $i-1$ ，需要将模式向右滑动一格，使得模式的第 1 个字符与新的文本位置 $i-1$ 对齐。

这个“模式向右滑动一格”在位向量中的表现就是：
原来表示“模式前 $k$ 个字符匹配”的位（位于位 $k-1$ ），现在应该表示“模式前 $k+1$ 个字符匹配”，因此它需要向左移动一位（从位 $k-1$ 移到位 $k$ ）。同时，最低位（位 0）补 0，表示还没有字符与新的文本位置匹配。

因此，左移一位 = 模式相对于文本向右滑动一个字符 = 消耗了一个模式字符。

以精确匹配为例（Line 13）：

R[0] = (oldR[0] \ll 1) \ | \ curPM

oldR[0] 是上一轮文本位置的状态。
oldR[0] << 1：将旧状态左移一位。
原来在位 $k-1$ 的匹配信息（表示模式前 $k$ 个字符已匹配）移动到位 $k$ ，表示模式前 $k+1$ 个字符已匹配。
最低位补 0，准备接收新模式字符的匹配信息。
curPM：当前文本字符对应的模式位掩码。
curPM 的位 0 表示当前文本字符是否与模式的第 1 个字符匹配；位 1 表示是否与第 2 个字符匹配……
通过与 curPM 做 OR，将当前文本字符与模式第 1 个字符的匹配情况填入最低位。

所以，左移操作完成了“模式向右滑动一格”，即消耗了一个模式字符。

论文 Figure 3 中模式为 "AC"，文本为 "AGC"， $k=1$ 。
初始 $R[0] = 11$ （两位全 1，无匹配）。

处理文本最后一个字符 'C'（位置 2）：

此时 R[0] 的位 1 为 1，表示从位置 2 开始，模式前两个字符未完全匹配。
左移操作把上一轮可能存在的部分匹配信息向左推进了一位，对应消耗了一个模式字符。

如果模式是向右滑动，在位向量中对应的是左移，因为位向量的索引方向与模式字符顺序一致（位 0 对应第一个字符）。
若采用相反的定义（位 0 对应最后一个字符），则左移和右移的含义会互换。但论文中明确采用“0 表示匹配”，且算法中左移操作与 curPM 的 OR 结合，符合上述解释。

因此，左移一位表示消耗一个模式字符，这是由位向量中位的位置与模式字符索引的对应关系以及文本遍历方向共同决定的。在 GenASM 中，由于支持长读长，位向量可能跨多个机器字，左移操作需要处理跨字的进位位，这也是论文第 5 节讨论的算法修改之一。