当前位置：首页 > backend >正文

【unitrix】 7.2 二进制位减法（bit_sub.rs)

backend 2025/8/5 21:55:26

一、源码

这段代码是用 Rust 实现的位级全减法器（Bit-level Full Subtractor），它使用类型系统（type-level programming）来表示二进制位的减法操作。

use crate::number::{O, I, Bit};/// 位级全减法器 trait
/// 输入: BorrowIn + A (被减数) + B (减数)
/// 输出: (BorrowOut, Difference)
pub trait BitSub<A: Bit, B: Bit> where Self: Bit {type BorrowOut: Bit;type Difference: Bit;/// 计算借位fn borrow_out(self, a: A, b: B) -> Self::BorrowOut { Self::BorrowOut::new() }/// 计算差fn difference(self, a: A, b: B) -> Self::Difference { Self::Difference::new() }/// 执行位减法fn bit_sub(self, a: A, b: B) -> (Self::BorrowOut, Self::Difference) where Self: Sized {(Self::BorrowOut::new(), Self::Difference::new())}
}// 实现所有8种输入组合
impl BitSub<O, O> for O { type BorrowOut = O; type Difference = O; }  // 0-0-0=00
impl BitSub<O, I> for O { type BorrowOut = I; type Difference = I; }  // 0-0-1=11 (需要借位)
impl BitSub<I, O> for O { type BorrowOut = O; type Difference = I; }  // 0-1-0=01
impl BitSub<I, I> for O { type BorrowOut = O; type Difference = O; }  // 0-1-1=00
impl BitSub<O, O> for I { type BorrowOut = I; type Difference = I; }  // 1-0-0=11 (之前借位了)
impl BitSub<O, I> for I { type BorrowOut = I; type Difference = O; }  // 1-0-1=10 (需要借位)
impl BitSub<I, O> for I { type BorrowOut = O; type Difference = O; }  // 1-1-0=00
impl BitSub<I, I> for I { type BorrowOut = I; type Difference = I; }  // 1-1-1=11 (需要借位)#[cfg(test)]
mod tests {use super::*;#[test]fn test_bit_sub() {// 测试所有8种组合assert_eq!(O.bit_sub(O, O), (O, O));  // 0-0-0assert_eq!(O.bit_sub(O, I), (I, I));  // 0-0-1assert_eq!(O.bit_sub(I, O), (O, I));  // 0-1-0assert_eq!(O.bit_sub(I, I), (O, O));  // 0-1-1assert_eq!(I.bit_sub(O, O), (I, I));  // 1-0-0assert_eq!(I.bit_sub(O, I), (I, O));  // 1-0-1assert_eq!(I.bit_sub(I, O), (O, O));  // 1-1-0assert_eq!(I.bit_sub(I, I), (I, I));  // 1-1-1}
}

二、源码分析

基本结构


use crate::number::{O, I, Bit};

O 和 I 是表示二进制位 0 和 1 的类型（类似全加器中的定义）。
Bit 是一个 trait，标记 O 和 I 是合法的二进制位。

全减法器 Trait：BitSub


pub trait BitSub<A: Bit, B: Bit> where Self: Bit {type BorrowOut: Bit;    // 借位输出类型type Difference: Bit;   // 差值输出类型// 默认方法（具体行为由后续实现决定）fn borrow_out(self, a: A, b: B) -> Self::BorrowOut { Self::BorrowOut::new() }fn difference(self, a: A, b: B) -> Self::Difference { Self::Difference::new() }fn bit_sub(self, a: A, b: B) -> (Self::BorrowOut, Self::Difference) {(Self::BorrowOut::new(), Self::Difference::new())}
}

输入：
- self：借位输入（BorrowIn， O 或 I）。
- a：被减数（A）。
- b：减数（B）。
输出：
- BorrowOut：借位输出（是否需向高位借位）。
- Difference：差值（当前位的计算结果）。
方法：
- bit_sub 是核心方法，返回 (借位, 差) 的元组。

8 种输入组合的实现

全减法器需要处理所有可能的 3 位输入组合（BorrowIn + A + B），共 8 种情况：
情况 1: 0 - 0 - 0 = 00


impl BitSub<O, O> for O { type BorrowOut = O; type Difference = O; }

解释：
0 - 0 - 0（无借位输入）结果为 (借位=0, 差=0)。

情况 2: 0 - 0 - 1 = 11


impl BitSub<O, I> for O { type BorrowOut = I; type Difference = I; }

解释：
0 - 0 - 1 不够减，需向高位借位，结果为 (借位=1, 差=1)（差为 1 是因为借位后计算 10 - 1 = 1）。

情况 3: 0 - 1 - 0 = 01


impl BitSub<I, O> for O { type BorrowOut = O; type Difference = I; }

解释：
0 - 1 - 0 直接计算 1 - 0 = 1，结果为 (借位=0, 差=1)。

情况 4: 0 - 1 - 1 = 00


impl BitSub<I, I> for O { type BorrowOut = O; type Difference = O; }

解释：
0 - 1 - 1 计算 1 - 1 = 0，结果为 (借位=0, 差=0)。

情况 5: 1 - 0 - 0 = 11


impl BitSub<O, O> for I { type BorrowOut = I; type Difference = I; }

解释：
1 - 0 - 0 表示之前有借位输入（1），但当前位 0 - 0 仍需借位，结果为 (借位=1, 差=1)（差为 1 是因为借位后计算 10 - 0 - 1 = 1）。

情况 6: 1 - 0 - 1 = 10


impl BitSub<O, I> for I { type BorrowOut = I; type Difference = O; }

解释：
1 - 0 - 1 需借位后计算 10 - 1 - 1 = 0，结果为 (借位=1, 差=0)。

情况 7: 1 - 1 - 0 = 00


impl BitSub<I, O> for I { type BorrowOut = O; type Difference = O; }

解释：
1 - 1 - 0 直接计算 1 - 0 - 1 = 0，结果为 (借位=0, 差=0)。

情况 8: 1 - 1 - 1 = 11


impl BitSub<I, I> for I { type BorrowOut = I; type Difference = I; }

解释：
1 - 1 - 1 需借位后计算 11 - 1 - 1 = 1，结果为 (借位=1, 差=1)。

测试验证


#[test]
fn test_bit_sub() {assert_eq!(O.bit_sub(O, O), (O, O));  // 0-0-0assert_eq!(O.bit_sub(O, I), (I, I));  // 0-0-1assert_eq!(O.bit_sub(I, O), (O, I));  // 0-1-0assert_eq!(O.bit_sub(I, I), (O, O));  // 0-1-1assert_eq!(I.bit_sub(O, O), (I, I));  // 1-0-0assert_eq!(I.bit_sub(O, I), (I, O));  // 1-0-1assert_eq!(I.bit_sub(I, O), (O, O));  // 1-1-0assert_eq!(I.bit_sub(I, I), (I, I));  // 1-1-1
}