教科书把进位和借位讲成两个东西，但在二进制里它们是同一个操作在加法与减法下的两种表现。理解这一点，立刻能解释几个让初学者困惑的现象：为什么模 的加法只需要一个加法器（丢掉进位即可，完全精确）；为什么模任意 的加法必须额外做一次比较与条件减法；以及为什么”模加法”在 Shor 类线路里才是真正的成本所在，而不是加法本身。
进位的布尔结构
第 位的全加器输出：
其中 是传入的进位， 是进位入。关键在于 maj（多数）是 、、 的多数票，而 。在可逆线路里，maj 要用 2 个 CNOT + 1 个 Toffoli 拼出来——这就是进位链里唯一昂贵的东西。
这张图是全站最值得逐列读一遍的线路：
- 前两列把
cin异或进a和b，此时两线存的分别是 与 ； - 第 3 列一个 Toffoli：，再异或进
cin就抵消掉末尾的 ，剩下 —— 正是多数。这也是整条进位链上唯一的 Toffoli； - 后两列用
cout把a、b各自异或一次，抵消掉开头的 ，两线复原为原始 、； - 最后一列 就是和位。
注意 cout 上那个 Toffoli：它是整条进位链的瓶颈。这也是为什么加法器的改进几乎全集中在”如何更便宜地实现这一段”——相对相位门、结构重排、分带近似，见CDKM 加法器与门代价模型。
借位就是进位
考虑二进制减法 。若把 按位取反加 1（），则
也就是说，减法被化成了两次操作：逐位取反（全是 NOT 门，便宜），然后加常数 1（只有最低位需要特殊处理，进位从此处开始）。这也是 negadd 名字的由来（negate and add，见negadd 与减法）。
进一步的观察：在 比特字长下， 与 逐位相同，因为丢弃的正是那一位借位出。所以模减法与模加法是同一个问题。
符号扩展（sign extension）也是同一族操作：把 的符号位 复制到所有更高位。复制 1 就是取反，复制 0 就是保持——这正是”加法器 + 一个全 1 常量”的效果。换句话说，符号扩展、加 1、减常数，都是同一个进位链在不同入口条件下的实例。
为什么模 加法是免费的
回看上面的全加器：它输出 与 。如果我们只要 而丢弃 ，那就得到了 ，且完全精确、无需任何额外操作。
这是量子算术里一个少见的”免费午餐”。它也是所有”模 加法器”论文的立足点。
对比一下模任意 的情况：
要得到模 的结果，必须：
- 先算 （ 位，可能溢出）；
- 判断 ；
- 若 ，则减去 （对选定的奇数模，只需减一次）。
第 2 步是比较，第 3 步是条件减法。两者都需要辅助比特与额外线路——这就是模加法在 Shor 类算法里成本高的真正原因。
比较器：被低估的那一步
模归约的瓶颈常常不是减法，而是比较 。实现上通常有两种：
- 借位链法：算 ，看借位出。 当且仅当无借位出。
- 前导零检测法：把 写成一个”掩码”，比较等价于检测差值的前导零个数，因此前导零检测器是模归约线路的核心子模块。
两种做法都需要 量级的辅助比特来承载中间差值，这也是各方案在”比特数 vs 深度”上分歧的根源。
取模与幂等：为什么只减一次
上面的第 3 步为什么减一次就够了？因为 ，所以 。因此
一次条件减法即达幂等。这也解释了为什么 Shor 里模 乘法的归约这一步”看起来简单”——它的简单性完全来自 为奇数这一前提。
三种加法的成本对照
| 运算 | 是否需要比较 | 辅助比特 | 精确性 |
|---|---|---|---|
| （第 位进位） | 否 | 1（就地） | 精确 |
| 否 | 1（就地） | 精确，免费丢弃进位 | |
| （ 奇数） | 是 | 精确 | |
| （归约） | 是 | 精确 |
这张表是理解全站成本结构的骨架：线性算术已经是位最优，它的成本全在辅助比特上；模算术的成本全在比较器上。
延伸阅读
- CDKM 加法器 —— 进位存进 的那条特定技巧
- negadd 与减法 —— 减法即取负相加
- 模加法 —— 比较器与条件减法的成本
- 比较器与相等判定 —— 第 2 步的细节
- 比特序与寄存器约定 —— 进位往哪个方向传