一、源码
这是一个使用 Rust 类型系统实现二进制数加一操作的代码。
use crate::number::{O, I, B, Null, Bit, NormalizeIf};
/// 类型级加一操作 trait
///
/// 为二进制数类型实现加一操作，返回新的类型
pub trait AddOne {
/// 加一操作的结果类型
type Output;
/// 执行加一操作
fn add_one(self) -> Self::Output;
}
// 基础类型实现 - 处理最简单的情况
impl AddOne for B<Null, O> {
type Output = B<B<Null, O>, I>; // 0 + 1 = 1
#[inline]
fn add_one(self) -> Self::Output {
B::new()
}
}
impl AddOne for B<Null, I> {
type Output = B<Null, O>; // -1 + 1 = 0
#[inline]
fn add_one(self) -> Self::Output {
B::new()
}
}
// 递归实现 - 处理通用二进制数
impl<H, L> AddOne for B<B<H, L>, O>
where
B<H, L>: NormalizeIf<I>, // 格式检查
{
type Output = <B<H, L> as NormalizeIf<I>>::Output;
#[inline]
fn add_one(self) -> Self::Output {
self.h.normalize(I) // 0 + 1 = 1，无进位，如果高位是N1时忽略I
}
}
impl<H, L> AddOne for B<B<H, L>, I>
where
B<H, L>: AddOne, // 高位部分需要能加一
<B<H, L> as AddOne>::Output: NormalizeIf<O>, // 有进位，如果高位是Z0时忽略O
{
type Output = <<B<H, L> as AddOne>::Output as NormalizeIf<O>>::Output;
#[inline]
fn add_one(self) -> Self::Output {
self.h.add_one().normalize(O) // 1 + 1 = 0 并进位
}
}
二、代码分析
- 核心概念
类型级编程：在编译期通过类型系统完成计算
二进制表示：使用嵌套的 B<H, L> 结构表示二进制数
H 是高位部分
L 是最低位（O=0 或 I=1）
加一操作：实现二进制数的递增运算
- 基础实现（简单情况）
对 0 加一：
impl AddOne for B<Null, O> { // 0
type Output = B<B<Null, O>, I>; // 0 + 1 = 1
fn add_one(self) -> Self::Output {
B::new() // 创建 B<B<Null,O>,I> 表示1
}
}
B<Null, O> 表示数字 0
加一后变为 B<B<Null,O>,I>（正数表示需要前导零）
对 -1 加一：
impl AddOne for B<Null, I> { // -1
type Output = B<Null, O>; // -1 + 1 = 0
fn add_one(self) -> Self::Output {
B::new() // 创建 B<Null,O> 表示0
}
}
B<Null, I> 表示数字 -1（补码表示）
加一后变为 B<Null, O>（0）
- 递归实现（通用情况）
最低位为 0 的情况：
impl<H, L> AddOne for B<B<H, L>, O> {
type Output = <B<H, L> as NormalizeIf<I>>::Output;
fn add_one(self) -> Self::Output {
self.h.normalize(I) // 0 + 1 = 1，可能产生进位
}
}
当最低位是 O(0) 时，加一只需将最低位变为 I(1)
使用 normalize(I) 标准化数的表示
最低位为 1 的情况：
impl<H, L> AddOne for B<B<H, L>, I> {
type Output = <<B<H, L> as AddOne>::Output as NormalizeIf<O>>::Output;
fn add_one(self) -> Self::Output {
self.h.add_one().normalize(O) // 1 + 1 = 0 并进位
}
}
当最低位是 I(1) 时，加一会产生进位
先对高位部分递归执行 add_one()
然后处理最低位置为 O(0)时的规范化
- 关键点说明
递归结构：
通过类型系统实现递归操作
从最低位开始处理，逐步向高位传播进位
NormalizeIf：
用于处理进位后的规范化
确保二进制表示的正确形式（如去除前导0后的连续0）
编译期计算：
所有计算都在编译期完成
运行时无额外开销
类型安全：
通过 trait bound 确保类型约束
防止非法操作
- 示例说明
B<B<Null,O>,I> (1) 加一：
最低位是 I，需要进位
对高位 B<Null,O> 加一得到 B<B<Null,O>,I>
最低位置为 O，结果为 B<B<B<Null,O>,I>,O> (2)
B<B<Null,I>,O> (-2) 加一：
最低位是 O，直接置为 I
高位为B<Null,I>,低位为I，需要规格化 (-1)
结果规格化为B<B<Null,I>,I>
这个实现展示了如何在 Rust 类型系统中实现数学运算，是类型级编程的典型示例。