【unitrix】 7.2 二进制位减法（bit

一、源码

这段代码是用 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-0
        assert_eq!(O.bit_sub(O, I), (I, I));  // 0-0-1
        assert_eq!(O.bit_sub(I, O), (O, I));  // 0-1-0
        assert_eq!(O.bit_sub(I, I), (O, O));  // 0-1-1
        assert_eq!(I.bit_sub(O, O), (I, I));  // 1-0-0
        assert_eq!(I.bit_sub(O, I), (I, O));  // 1-0-1
        assert_eq!(I.bit_sub(I, O), (O, O));  // 1-1-0
        assert_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-0
    assert_eq!(O.bit_sub(O, I), (I, I));  // 0-0-1
    assert_eq!(O.bit_sub(I, O), (O, I));  // 0-1-0
    assert_eq!(O.bit_sub(I, I), (O, O));  // 0-1-1
    assert_eq!(I.bit_sub(O, O), (I, I));  // 1-0-0
    assert_eq!(I.bit_sub(O, I), (I, O));  // 1-0-1
    assert_eq!(I.bit_sub(I, O), (O, O));  // 1-1-0
    assert_eq!(I.bit_sub(I, I), (I, I));  // 1-1-1
}

测试覆盖所有 8 种输入组合，验证输出是否符合预期。

三、关键点总结

类型级编程：通过 Rust 的类型系统在编译期完成计算，无需运行时开销。
借位逻辑：

当 A < B + BorrowIn 时，BorrowOut = 1（需向高位借位）。
差值计算考虑借位后的结果（如 10 - B - BorrowIn）。

扩展性：可组合多个 BitSub 实现多位减法器（类似全加器级联）。

这个实现展示了如何用 Rust 的类型系统优雅地建模硬件电路中的减法操作！

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

一、源码

二、源码分析

三、关键点总结

网站公告

今日签到

热门文章

最新发布