用Rust写平衡三进制除法器
1、除法的本质
除法的本质是减法，也就是一个大的数减去一个小的数，比如:10/2，也就是10-2-2-2-2-2=0，所以商5余0，10/3，也就是10-3-3-3=1，所以商3余1，这也是很常见的方法，但如果引入负数，情况又会有些变化，分成4种总结为2种:
10/2=10-(2*1)-2-2-2-2=0 商5余0，
-10/-2=-10-(-2*1)+2+2+2+2=0 商5余0，
10/-2=10-(-2*-1)-2-2-2-2=0 商-5余0，
-10/2=-10-(2*-1)+2+2+2+2=0 商-5余0，
通过上面示例，可看出双正双负，得的商是正数，而一正一负，得的商是负数，仔细看10/-2及-10/2这两个例子，拿10/-2举例，10-(-2)=12越来越大了，与实际情况不符，所以要乘于-1即，10-(-2*-1)=8与实际情况相符，所以商是负数正确；对于平衡三进制同样适用，被除数与除数相减后变余数，被除数(余数)与除数同种符号，上1反之上T，这样才能保证两者越来越趋向于0，所以最简单粗暴方法就是，用减法来做加法 ，详情请看：二进制如何做除法？及 平衡三进制四则运算 文章。
2、平衡三进制除法器：减法器版
平衡三进制的好处就是对称，但也特别的有特点，比如它的减法器，在平衡三进制加法器中它是正向进位的，而减法器它可以负向进位，你没听错是负向进位，当初的我算也不会算，后面得益于我的初中知识，有公式：被减数 + 取反的要减数= 被减数 - 要减数，即12-6=6相当于12+(-6)=6，负负得正了，这确很方便了，只要被减数加上取反的要减数，就可以得到结果，但其实它的减法表也是可以用，不过太反直觉了，并不建议使用，减法器版除法器，原理如下所示：
可得代码：
// **非门(TNEG)逻辑表 输入T，输出1；输入0，输出0；输入1，输出T；**
const TNEG:[u8; 3]= [0, 2, 1];
// **非零门(TPOZ)逻辑表 当为T1、0T、T0、TT时出T，当为1T、01、10、11时出1，双0出0 此门用于检测其最高位的正负性，出T为负数，出1为正数，出0则0 **
const TPOZ:[[u8; 3];3]= [
[0, 1, 2],
[1, 1, 1],
[2, 2, 2],
];
// **加和(TSUM)逻辑表 当为TT、01、10时出1，当为11、0T、T0时出T，其余为0 此门用于半加器的加和位处理 **
const TSUM:[[u8; 3];3]= [
[0, 1, 2],
[1, 2, 0],
[2, 0, 1],
];
// **共识(TCONS)逻辑表 双T出T、双1出1、其余为0 此门用于半加器的进位处理 **
const TCONS:[[u8; 3];3]= [
[0, 0, 0],
[0, 1, 0],
[0, 0, 2],
];
// **全加器和(TFULLSUM) 逻辑表**
const TFULLSUM:[[[u8; 3];3];3] = [
[
[0, 1, 2],
[1, 2, 0],
[2, 0, 1],
],
[
[1, 2, 0],
[2, 0, 1],
[0, 1, 2],
],
[
[2, 0, 1],
[0, 1, 2],
[1, 2, 0],
],
];
// **全加器进位(TFULLCONS) 逻辑表**
const TFULLCONS:[[[u8; 3];3];3] = [
[
[0, 0, 0],
[0, 1, 0],
[0, 0, 2],
],
[
[0, 1, 0],
[1, 1, 0],
[0, 0, 0],
],
[
[0, 0, 2],
[0, 0, 0],
[2, 0, 2],
],
];
/// 判断三进制数的符号（从高位到低位）
/// - 返回 0 表示全 0
/// - 返回 1 表示正数（首个非零位是 1）
/// - 返回 2 表示负数（首个非零位是 T）
pub fn ternary_sign(stack: &[u8]) -> u8 {
let mut state: u8 = 0;
for &digit in stack {
state = TPOZ[state as usize][digit as usize];
}
state
}
/// 获取相反数
pub fn ternary_tneg(stack: Vec<u8>)-> Vec<u8>{
stack.iter().map(|&x| TNEG[x as usize]).collect()
}
/// 半加器：返回 (sum, carry)
pub fn ternary_half_adder(a: u8, b: u8) -> (u8, u8) {
let sum = TSUM[a as usize][b as usize];// 和
let carry=TCONS[a as usize][b as usize];// 进位;
(sum, carry)
}
/// 全加器：基于三维数组实现
pub fn ternary_full_adder(a: u8, b: u8, c_in: u8) -> (u8, u8) {
let sum =TFULLSUM[a as usize][b as usize][c_in as usize];// 和
let carry=TFULLCONS[a as usize][b as usize][c_in as usize];// 进位
(sum, carry)
}
/// 多位三进制累加器
pub fn ternary_stack_accumulate(mut stack: Vec<u8>,mut c_in: u8)-> Vec<u8>{
let mut result:Vec<u8> = Vec::new();//存储和
while let Some(v1) = stack.pop() {
let (s_out, next_carry) = ternary_half_adder(v1, c_in);
result.push(s_out);//存结果
c_in = next_carry;//进位传递
}
if c_in!=0{
result.push(c_in);// 推入最高位
}
result.reverse(); // 反转，从高位到低位排列
result
}
/// 多位三进制加法器,输入两个的三进制向量，返回加法结果向量和最终进位
fn ternary_stack_adder(mut stack1: Vec<u8>,mut stack2: Vec<u8>)-> Vec<u8>{
let mut result:Vec<u8> = Vec::new();//存储和
let mut c_in:u8=0;
//Rust标准库中Vec，用栈协同弹出，倒序遍历, 支持不同长度
while !stack1.is_empty() || !stack2.is_empty() {
let v1 = stack1.pop().unwrap_or(0);
let v2 = stack2.pop().unwrap_or(0);
let (s_out, next_carry) =ternary_full_adder(v1, v2, c_in);
result.push(s_out);//存结果
c_in=next_carry;//进位传递
}
if c_in!=0{
result.push(c_in);// 推入最高位
}
result.reverse(); // 反转，从高位到低位排列
result
}
/// 多位三进制乘法器
pub fn ternary_mul_base(stack1: Vec<u8>, stack2: Vec<u8>)-> Vec<u8>{
// 构建偏积表：分别是乘以 0, 1, T 的情况
let partials = vec![
vec![0; stack1.len()], //0乘任何数，都得0
stack1.clone(), //任何数乘1，等于它本身
ternary_tneg(stack1), //任何数乘T(-1)等于相反数
];
let mut result: Vec<u8> = vec![0];
for (shift, &m2) in stack2.iter().rev().enumerate() {
let mut part = partials[m2 as usize].clone();//用偏积表，m2当成下标,出可变副本
part.resize(part.len() + shift, 0); // 更高效的偏移，低位补 0
result = ternary_stack_adder(result, part);//加入当前部分积
}
result
}
///多位三进制除法器：累加版
pub fn ternary_div_base(stack1: Vec<u8>, stack2: Vec<u8>)-> (Vec<u8>,Vec<u8>){
let sign_divided=ternary_sign(&stack1);//最初被除数符号
let sign_divisor=ternary_sign(&stack2);//除数符号
// 零不能作为除数
if sign_divisor == 0 {
panic!("零不能作为除数");
}
//零除于任何非零数都等于零
if sign_divided == 0{
return (vec![0], vec![0]);
}
let is_equal=sign_divided==sign_divisor;
//被除数与除数，要互为相反数，先将被除数取反，一直加直到加回来
let mut remainder = if is_equal{ternary_tneg(stack1)}else{stack1};
let digit = if is_equal { 1 } else { 2 }; //同符号上1，反之上T
let mut count = 0;//统计加了多少次
loop{
let current_sign=ternary_sign(&remainder);//获取当前被除数符号
if current_sign==sign_divisor{//如果加回来，被除数与除数符号相同
//撤回上一步结果
count -= 1;
if is_equal{
remainder=ternary_stack_adder(ternary_tneg(remainder), stack2.clone());
}else {
remainder=ternary_stack_adder(ternary_tneg(stack2.clone()), remainder);
}
break;
}
count += 1;
remainder = ternary_stack_adder(remainder, stack2.clone());//取反的被除数不断加除数
}
//构建最终商
let mut quotient = vec![0];
for _ in 0..count {
quotient = ternary_stack_accumulate(quotient, digit);
}
//商、余数
(quotient,remainder)
}
fn main() {
let stack1=vec![1,0,1];
let stack2=vec![1,0];
let re=ternary_div_base(stack1,stack2);
println!("商和余数:{:?}",re);
let stack1=vec![2,0,2];
let stack2=vec![2,0];
let re=ternary_div_base(stack1,stack2);
println!("商和余数:{:?}",re);
let stack1=vec![2,0,2];
let stack2=vec![1,0];
let re=ternary_div_base(stack1,stack2);
println!("商和余数:{:?}",re);
let stack1=vec![1,0,1];
let stack2=vec![2,0];
let re=ternary_div_base(stack1,stack2);
println!("商和余数:{:?}",re);
}3、平衡三进制二重商除法
刚开始算了很多次，都无从下手，我差点就觉得它压根算不了，直到我看到了这文章托马斯·福勒的三元计算机，确实可以算，但是不知其运算规则，如下图所示：
它算的是280/5=35，过程很清楚，即216+72+0+8=280，中间结果余数是允许有负的，就像上面的-8，这里有三个点要注意，首先是减法太麻烦了，当商上+时，应是写成(+0++0+)-(+0-000)，现在变成了(+0++0+)+(-0+000)，这就是相减变成加上它的相反数，所以商为+时，出相反数，商为-时，直接照样写；然后就是对位要齐，若对不齐就会导致算错，这里+0-后面，跟了多少个0，每多1个0，那就要多乘3，可出列表格：
| 平衡三进制数 | 十进制 |
| +0-000 | 216（8*3*3*3） |
| +0-00 | 72（8*3*3） |
| +0- | 8 |
还有就是商要怎么上，就是要余数趋于0，规则如下所示：
被除数(余数)与除数互为相反数，商就上- ；
被除数(余数的最高位是0)，商上0，本轮跳过；
被除数(余数)与除数同种符号，都为正数或负数，商就上+；
感觉学会了，下面来用一下吧，比如10/2和4/2的平衡三进制除法：
没想到吧，10/2可以取18这个数，比10都大，但是结果就是正确的，其它都不行，这是怎么想到的，也就是+-后面加0，即+-为2、+-0为6、+-00为18，商是+--，所以结果是18-6-2=10，也就是10-18+6+2=0；同样的，4/2相当于4-6+2=0，商就是（+-）。
这个是我最觉得离谱的事实，当时我还在费尽心机的，寻找这个除法的最小商，百思不得其解，上述参考托马斯·福勒写的算式，也不知道除数，什么时候要加前置0，直到今天我写出了这平衡三进制除法文章，终于知道了这平衡三进制离谱的事实，和简单到小学数字的程度。
平衡三进制最小商：就是除数本身与商的乘积。为什么这样说，一个数只乘于(-1/0/1)，怎么乘还是本身或其相反数，更离谱的是，我发现平衡三进制除法，压根不用对比余数大小，只要判断余数的最高位是否为0就可以了，但特别的是，同一位置至多可上二次商，下面用之前的三个例子，来说明此种情况：
最开始的时候，我压根想不到会有二重商这么骚的操作，同一位置可以上两次商，那什么时候上二重商，那就当执行了一次减法后，余数的最高位不为0，则还要减一次，而这里的相减则是加上相反数，同符号(++与--)商上+取除数相反数，不同符号(+-与-+)商上-取除数相等数，若余数最高位是0，商则上0，本轮跳过，如上面的+0+与+-的除法运算：
+0与+-同符号，商上+相减得0+，余数最高位是0则下一位，移1位变0++；然后++与+-同符号，商上+相减得+-，最高位不为0，+-与+-同符号，二次上商+，没有下一位了，得结果+--
还有是+0++0+与+0-的除法：
先是+0+与+0-，商上+相减得0+-，余数最高位是0下一位，拉一位变+-+；然后+-+与+0-，商上+相减得00-，余数最高位是0下一位，拉一位变0-0；然后0-0与+0-，余数最高位是0，不用减，直接下一位，拉一位变-0+；然后-0+与+0-，不同符号商上-，相减得0，最终结果++0-
最后是++与+-的除法：
先是++与+-同符号，商上+相减得+-，最高位不为0，二次上商，+-与+-同符号，二次上商+相减得0，且除数也用完，除法完成，即+-
这个方法是通用的，我想了好久，真离谱有二重商的除法，连大小都不用对比，也辛亏了高德纳写的文章，参考它的方法改进出此方法，不然去找它的大小关系，一会正数一会负数，余数有正又有负的，判断起来那还不如用十进制，但此方法不用对比大小，直接按规则出答案，简直不讲道理，简单的一批，以下是一此算式：
4、九九乘法表：拼好数版
将九九乘法表，转成了平衡三进制的版本，发现一些有趣的特性，那就是拼好数，例如：
5、平衡三进制除法器：试商版
说实话，其实这才是最常用的，就像10/2=5，没人会10-2-2-2-2-2=0这样算，但对于平衡三进制来说，不理解它的话，那就去看机械时代的计算这篇文章，详细说了如何算，还有上商的规则：双正双负商是正的，一正一负商是负，其余的商是0（也就是对不齐位的情况，0与正负数），也就是出现了这除法表，其中0/1/2表示0/1/T，而3表示非法值，如下所示：
| T | 0(0不能作为除数) | 1 | |
|---|---|---|---|
| T | 1 | 3 | T |
| 0 | 0 | 3 | 0 |
| 1 | T | 3 | 1 |
可得代码如下（这有个致命错误++++/+0-，解决方法是改判断条件）：
// **非门(TNEG)逻辑表 输入T，输出1；输入0，输出0；输入1，输出T；**
const TNEG:[u8; 3]= [0, 2, 1];
// **比较门(TCMP)逻辑表 （a=b）输出 0、 （a > b）输出 +1、(a < b)输出 -1**
pub const TCMP:[[u8; 3];3]= [
[0, 2, 1],
[1, 0, 1],
[2, 2, 0],
];
// **除法门(TDIV)逻辑表 零不能作为除数，3属于非法值**
pub const TDIV:[[u8; 3];3]= [
[3, 0, 0],
[3, 1, 2],
[3, 2, 1],
];
// **全加器和(TFULLSUM) 逻辑表**
const TFULLSUM:[[[u8; 3];3];3] = [
[
[0, 1, 2],
[1, 2, 0],
[2, 0, 1],
],
[
[1, 2, 0],
[2, 0, 1],
[0, 1, 2],
],
[
[2, 0, 1],
[0, 1, 2],
[1, 2, 0],
],
];
// **全加器进位(TFULLCONS) 逻辑表**
const TFULLCONS:[[[u8; 3];3];3] = [
[
[0, 0, 0],
[0, 1, 0],
[0, 0, 2],
],
[
[0, 1, 0],
[1, 1, 0],
[0, 0, 0],
],
[
[0, 0, 2],
[0, 0, 0],
[2, 0, 2],
],
];
/// 获取相反数
pub fn ternary_tneg(stack: Vec<u8>)-> Vec<u8>{
stack.iter().map(|&x| TNEG[x as usize]).collect()
}
/// 比较两个平衡三进制大小（从高位到低位,位数要相同）
/// - 返回 0 表示相等
/// - 返回 1 表示 a > b
/// - 返回 2 表示 a < b
/// 向量：返回 2(T), 0, 1
pub fn ternary_cmp(stack1: &[u8], stack2: &[u8]) -> u8 {
let mut state: u8 = 0;
for (&a, &b) in stack1.iter().zip(stack2.iter()) {
state=TCMP[a as usize][b as usize];
if state!=0{break;}//全部对比过，则相等
}
state
}
/// 判断是否在半封闭区间(neg与pos互为相反数)，是则True,反之False
fn in_open_interval(x: &[u8],neg: &[u8],pos: &[u8]) -> bool {
// 判断 x ∈ (min, max)
ternary_cmp(neg, x)==ternary_cmp(x, pos)
}
/// 全加器：基于三维数组实现
fn ternary_full_adder(a: u8, b: u8, c_in: u8) -> (u8, u8) {
let sum =TFULLSUM[a as usize][b as usize][c_in as usize];// 和
let carry=TFULLCONS[a as usize][b as usize][c_in as usize];// 进位
(sum, carry)
}
/// 多位三进制加法器,输入两个的三进制向量，返回加法结果向量和最终进位
pub fn ternary_stack_adder(mut stack1: Vec<u8>,mut stack2: Vec<u8>)-> Vec<u8>{
let mut result:Vec<u8> = Vec::new();//存储和
let mut c_in:u8=0;
//Rust标准库中Vec，用栈协同弹出，倒序遍历, 支持不同长度
while !stack1.is_empty() || !stack2.is_empty() {
let v1 = stack1.pop().unwrap_or(0);
let v2 = stack2.pop().unwrap_or(0);
let (s_out, next_carry) =ternary_full_adder(v1, v2, c_in);
result.push(s_out);//存结果
c_in=next_carry;//进位传递
}
if c_in!=0{
result.push(c_in);// 推入最高位
}
result.reverse(); // 反转，从高位到低位排列
result
}
//两步试商法 传入被除数与除数及商的位移值
pub fn ternary_div_step(mut remainder: Vec<u8>,mut quotient: Vec<u8>,divisor: &[u8], shift: usize)->(Vec<u8>,Vec<u8>){
let digit=TDIV[remainder[0] as usize][divisor[0] as usize];//获取商的符号
if digit==3{panic!("零不能作为除数");}
if digit==0{return (remainder,quotient);}//商为0,直接返回
// 先构造商位，位置靠左
let mut current_quot = vec![digit];
current_quot.resize(shift + 1, 0);
let delta=if digit==1{ternary_tneg(divisor.to_vec())}else{divisor.to_vec()};
let neg_div = ternary_tneg(divisor.to_vec());
//第一轮减法
remainder=ternary_stack_adder(remainder,delta.clone());
//if !in_open_interval(&remainder, &neg_div,&divisor)//未符合半封闭区间，第二轮减法,压根不用比
if remainder[0] != 0{
current_quot=ternary_stack_adder(current_quot.clone(),current_quot);//双倍商
remainder=ternary_stack_adder(remainder,delta);
}
quotient=ternary_stack_adder(quotient, current_quot);
//余数、商
(remainder,quotient)
}
///多位三进制除法器：判断版
pub fn ternary_div_choose(stack1: Vec<u8>, stack2: Vec<u8>)-> (Vec<u8>,Vec<u8>){
let divisor_len=stack2.len();
let mut quotient = vec![0];
//被除数分成两个向量 p 和 s，位数最多与除数 (q) 相同，s 是剩余位数的向量
let (mut remainder, mut s)= (stack1[..divisor_len].to_vec(),stack1[divisor_len..].to_vec());
let fixed=s.len();
for shift in 0..=fixed{
// 调用试商逻辑：返回 (新的余数, 当前商位)
(remainder,quotient ) = ternary_div_step(remainder, quotient,&stack2,fixed-shift);
println!("bb{:?}{:?}{:?}",remainder,quotient,s);
if !s.is_empty() {
remainder.remove(0);// 左移一位
remainder.push(s[0]);// 拉一位进来
s.remove(0);// s 去掉这一位
}
}
(quotient,remainder)
}
fn main() {
let stack1=vec![1,0,1];//10/-2
let stack2=vec![2,1];
let re=ternary_div_choose(stack1,stack2);
println!("商和余数:{:?}",re);
let stack1=vec![1,0,1];//10/3
let stack2=vec![1,0];
let re=ternary_div_choose(stack1,stack2);
println!("商和余数:{:?}",re);
let stack1=vec![1,2,1,1,2];//65/5
let stack2=vec![1,2,2];
let re=ternary_div_choose(stack1,stack2);
println!("商和余数:{:?}",re);
let stack1=vec![1,0,1,1,0,1];//280/8
let stack2=vec![1,0,2];
let re=ternary_div_choose(stack1,stack2);
println!("商和余数:{:?}",re);
let stack1=vec![1,2,1,1];//22/-5
let stack2=vec![2,1,1];
let re=ternary_div_choose(stack1,stack2);
println!("商和余数:{:?}",re);
}运行结果正确，如下所示：
智能硬件社区聚焦AI智能硬件技术生态，汇聚嵌入式AI、物联网硬件开发者，打造交流分享平台，同步全国赛事资讯、开展 OPC 核心人才招募，助力技术落地与开发者成长。
更多推荐
14
0- 0
已为社区贡献3条内容
所有评论(0)