【PhysUnits】13 改进减法(sub.rs)

源码

这段代码实现了一个类型级别的二进制数减法系统，通过 Rust 的特质(trait)系统在编译期完成计算。

use core::ops::{Neg, Not, Sub};
use super::basic::{B0, B1, Z0, N1, Integer, NonZero, NonNegOne};
use super::add1::Add1;
use super::sub1::Sub1;
use super::standardization::{IfB0, IfB1};


// ==================== 带借位减法 Trait ====================
/// 带借位减法运算
/// Subtraction with borrow operation
///
/// 表示 a - b - 1 的运算 (相当于 a - (b + 1))
/// Represents the operation of a - b - 1 (equivalent to a - (b + 1))
pub trait SubWithBorrow<Rhs> {
    type Output;
}

// ==================== 带借位减法实现 ====================

// Z0 - I (带借位) = !I (!I+1-1)
impl<I:Integer + Not> SubWithBorrow<I> for Z0 {
    type Output = I::Output;
}

// I - Z0 (带借位) = I-1
impl<I: NonZero + Sub1> SubWithBorrow<Z0> for I{
    type Output = I::Output;
}

// N1 - I (带借位,非0) = !I-1 (即N1+（!I+1）-1)
impl<I: NonZero + Not> SubWithBorrow<I> for N1
where
    <I as Not>::Output:Sub1,
{
    type Output = <I::Output as Sub1>::Output;
}

// I - N1 (带借位) = I
impl<I: NonZero + NonNegOne> SubWithBorrow<N1> for I {
    type Output = I;
}

// B0 - B0 (带借位)
impl<H1: Integer + SubWithBorrow<H2>, H2: Integer> SubWithBorrow<B0<H2>> for B0<H1>
where
    H1::Output: IfB1,
{
    type Output = <H1::Output as IfB1>::Output;
}

// B0 - B1 (带借位)
impl<H1: Integer + SubWithBorrow<H2>, H2: Integer> SubWithBorrow<B1<H2>> for B0<H1>
where
    <H1 as SubWithBorrow<H2>>::Output: IfB0,
{
    type Output = <H1::Output as IfB0>::Output;
}

// B1 - B0 (带借位)
impl<H1: Integer + Sub<H2>, H2: Integer> SubWithBorrow<B0<H2>> for B1<H1>
where
    <H1 as Sub<H2>>::Output: IfB0,
{
    type Output = <H1::Output as IfB0>::Output;
}

// B1 - B1 (带借位)
impl<H1: Integer + SubWithBorrow<H2>, H2: Integer> SubWithBorrow<B1<H2>> for B1<H1>
where
    <H1 as SubWithBorrow<H2>>::Output: IfB1,
{
    type Output = <H1::Output as IfB1>::Output;
}

// ==================== 标准减法实现 (Sub trait) ====================

// Z0 - I = -I
impl<I: Integer + Neg> Sub<I> for Z0 {
    type Output = I::Output;
    fn sub(self, _: I) -> Self::Output {
        Self::Output::new()
    }
}

// I - Z0 = I,I=N1、B0、B1
impl Sub<Z0> for N1 {
    type Output = N1;
    fn sub(self, _: Z0) -> Self::Output {
        N1::new()
    }
}
impl<H: Integer> Sub<Z0> for B0<H> {
    type Output = B0<H>;
    fn sub(self, _: Z0) -> Self::Output {
        B0::new()
    }
}
impl<H: Integer> Sub<Z0> for B1<H> {
    type Output = B1<H>;
    fn sub(self, _: Z0) -> Self::Output {
        B1::new()
    }
}

// N1 - 非0 = ！I
impl<I: NonZero + Not> Sub<I> for N1 {
    type Output = I::Output;
    fn sub(self, _: I) -> Self::Output {
        Self::Output::new()
    }
}

// B0、B1 - N1
impl<H: NonNegOne> Sub<N1> for B0<H> {
    type Output = B1<H>;
    fn sub(self, _: N1) -> Self::Output {
        Self::Output::new()
    }
}

impl Sub<N1> for B0<N1> {
    type Output = N1;
    fn sub(self, _: N1) -> Self::Output {
        N1::new()
    }
}

// B1<H> - N1 = B0<H>
impl<H: Integer + Add1> Sub<N1> for B1<H> {
    type Output = B0<H::Output>;
    fn sub(self, _: N1) -> Self::Output {
        Self::Output::new()
    }
}

// B0 - B0
impl<H1: Integer + Sub<H2>, H2: Integer> Sub<B0<H2>> for B0<H1>
where
    <H1 as Sub<H2>>::Output: IfB0,
{
    type Output = <H1::Output as IfB0>::Output;
    fn sub(self, _: B0<H2>) -> Self::Output {
        Self::Output::new()
    }
}

// B0 - B1 (需要借位)
impl<H1: Integer + SubWithBorrow<H2>, H2: Integer> Sub<B1<H2>> for B0<H1>
where
    <H1 as SubWithBorrow<H2>>::Output: IfB1,
{
    type Output = <H1::Output as IfB1>::Output;
    fn sub(self, _: B1<H2>) -> Self::Output {
        Self::Output::new()
    }
}

// B1 - B0
impl<H1: Integer + Sub<H2>, H2: Integer> Sub<B0<H2>> for B1<H1>
where
    <H1 as Sub<H2>>::Output: IfB1,
{
    type Output = <H1::Output as IfB1>::Output;
    fn sub(self, _: B0<H2>) -> Self::Output {
        Self::Output::new()
    }
}

// B1 - B1
impl<H1: Integer + Sub<H2>, H2: Integer> Sub<B1<H2>> for B1<H1>
where
    <H1 as Sub<H2>>::Output: IfB0,
{
    type Output = <H1::Output as IfB0>::Output;
    fn sub(self, _: B1<H2>) -> Self::Output {
        Self::Output::new()
    }
}

二、基本概念

1. 类型表示：

• Z0：表示数字 0

• B0：表示二进制数末尾是 0 的数（相当于 H << 1）

• B1：表示二进制数末尾是 1 的数（相当于 (H << 1) + 1）

• N1：表示 -1

2. 核心特质：

• SubWithBorrow：带借位的减法（计算 a - b - 1）

• Sub：标准减法（计算 a - b）

三、带借位减法实现 (SubWithBorrow)

1. 零减去任何数：

impl<I: Integer + Not> SubWithBorrow<I> for Z0 {
    type Output = I::Output;  // !I
}

0 - I - 1 = -(I + 1) = !I（因为 !I 在二进制补码中表示 -I - 1）

2. 任何数减去零：

impl<I: NonZero + Sub1> SubWithBorrow<Z0> for I {
    type Output = I::Output;  // I - 1
}

I - 0 - 1 = I - 1

3. -1 减去任何非零数：

impl<I: NonZero + Not> SubWithBorrow<I> for N1 {
    type Output = <I::Output as Sub1>::Output;  // !I - 1
}

-1 - I - 1 = -(I + 2) = !I - 1

4. 任何数减去 -1：

impl<I: NonZero + NonNegOne> SubWithBorrow<N1> for I {
    type Output = I;  // I
}

I - (-1) - 1 = I

5. 二进制数之间的带借位减法：
   处理不同组合的二进制数相减（B0/B1 的各种组合），递归处理高位并考虑借位情况。

四、标准减法实现 (Sub)

1. 零减去任何数：

impl<I: Integer + Neg> Sub<I> for Z0 {
    type Output = I::Output;  // -I
}

2. 任何数减去零：

impl Sub<Z0> for N1 {
    type Output = N1;  // -1
}
impl<H: Integer> Sub<Z0> for B0<H> {
    type Output = B0<H>;  // 保持原值
}
impl<H: Integer> Sub<Z0> for B1<H> {
    type Output = B1<H>;  // 保持原值
}

3. -1 减去任何非零数：

impl<I: NonZero + Not> Sub<I> for N1 {
    type Output = I::Output;  // !I
}

-1 - I = -(I + 1) = !I

4. 二进制数减去 -1：

impl<H: NonNegOne> Sub<N1> for B0<H> {
    type Output = B1<H>;  // 相当于加1
}
impl Sub<N1> for B0<N1> {
    type Output = N1;  // 特殊情况处理
}
impl<H: Integer + Add1> Sub<N1> for B1<H> {
    type Output = B0<H::Output>;  // 相当于加1后变为B0
}

5. 二进制数之间的减法：
   处理 B0/B1 的各种组合，递归处理高位，必要时使用带借位减法。

五、设计特点

1. 类型安全：所有操作在编译期完成，运行时无开销。

2. 递归处理：通过递归处理二进制数的高位部分。

3. 特殊情况处理：对 0 和 -1 有专门的处理逻辑。

4. 借用机制：通过 SubWithBorrow 处理减法中的借位情况。

这个系统展示了 Rust 类型系统的强大能力，可以在编译期完成复杂的数学运算验证。